O(n) of solution to solve boggle

Question

What is the best time complexity O(n) of a function that solves boggle, where the boggle board is n by n?

I feel that it's n^2 since for each character we must look at 2(n-1) other characters. The interviewer argued that it's not n^2 for an O(1) dictionary look-up.

Answer 1

It's not very clear what the dictionary is capable of.

A bit silly but in my opinion correct answer is as follows:

Since in boggle, words can go arbitrary ways (from each character to any adjacent (horizontal, vertical or diagonal) characters not already used in this word), for a word of length L, the cominations of words can be up to 8^L unless you eliminate the combinations where characters appear multiple times. Anyway, considering L to be constant (as the used dictionary is constant), this value is constant too. To sum up, finding word(s) starting from a given position has a time complexity of O(1).

So what remains is the start position of the word, which is in the space n^2, so your boggle solver has time complexity of O(n^2) and you are right.

As said before, I think this argumentation is a bit silly.

The problem might be that one doesn't want to consider the dictionary to be constant, because it is very large. Assuming it to be infinitely large but it implements a O(1) look-up for existing words (which is the ONLY query we can use for the dictionary, especially there is no look-up for word prefixes), and further assuming n not to be a limiting factor in comparison to the word lengths, time complexity is exponential. But I think the assumption that the look-up only succeeds for existing words is false in this exercise.

Another possible assumption would be, that the dictionary has a look-up for word prefixes (which returns whether there exist words which start with the given string but are not necessarily equal to the string). In this case, we could implement a better and far more complex algorithm which searches the limited search space (using each character at most once). A limiting factor of word lengths would be n^2, since no word (contained in the current boggle board) can be longer than that (because we can use each character only once). Again the start positions are in space n^2, so a stupid path-based algorithm would have a time complexity of O(n^4), so you are wrong. Currently, I can't think of an algorithm with better time complexity under this assumptions.