if we use brute force we have sum(n + n-1 + .. n-r .. + 1) = n*n words which
are to be checked. Therefore O(n-sq).
now, if i can use a dictionary interface to reject some prefix altogether,
than i need not check some words, o/w with the given interface we cannot do
it any better than quadratic
What is the source of this question?
On Sep 20, 4:49 am, Ankur Garg ankurga...@gmail.com wrote:
nice find bhanu..though i didnt get much :P on first read :D :D
On Tue, Sep 20, 2011 at 4:34 AM, Bhanu Kishore
bhanukishor...@gmail.comwrote:
See this algorithm:
Assuming that findword is O(n) for words of size n, this will be an
O(n^3) algorithm. If you had a better interface to the dictionary, it
could be O(n). That's another example of why interfaces should be
designed for the intended task.
Don
On Sep 19, 9:50 am, Sangeeta sangeeta15...@gmail.com
