We are requiring that your search function run in O(log(i+j)). However, our official solution can actually search in time more or less independant of the size of the index. The running time of the sample solution is entirely dependent on the properties of the specific search. These properties include the number of keywords in the query, the length of each of these words, and the number of results returned. This last parameter will probably grow as the number of pages in the index grows, but if you're clever and very careful about how you implement your index structure, you can even eliminate this dependance.
So if you search for m keywords, each with an average length of k characters, how might you search (and remember we need to prioritize!) in O(m*k*f(n)) time? Here, n is the number of pages returned, not the number of pages in the index. f is some function of n (n, n^2, n*log(n), etc.). |