Problem Detail: Looking something up in an unsorted list is a task with time complexity $O(n)$. However, if the list is sorted, the time complexity is $O(log(n))$. That means it is sometimes worthwhile to sort an array. However, that is a trade-off as a sorting algorithm has a time complexity of $O(nlog(n))$. As far as I know, you can not sort an array in less than $O(nlog(n))$ time. I am however wondering if there is any algorithm that can partially sort the array in less time than that? I am pretty sure you can not look up a value in such a partially sorted array in $O(log(n))$ time, but can you do better than $O(n)$? In short, is it possible to process an unsorted array with an algorithm faster than $O(nlog(n))$ such that a lookup algorithm can do a search faster than $O(n)$, though not as fast as $O(log(n))$?
Asked By : Hohmannfan
Answered By : Yuval Filmus
If you run “balanced Quicksort” (using the exact median at every step) up to depth $k$ (at the cost of $O(n k)$), you get a partition of the original array into $2^k$ sorted parts of $n/2^k$ unsorted elements each. Given an element, we can locate the correct part in time $O(log(2^k)) = O(k)$ using binary search, and then look it up using an additional $O(n/2^k)$, for a total complexity of $O(n/2^k + k)$. If $k = o(log n)$ then the partial sorting takes time $o(nlog n)$. If $k = omega(1)$ then the lookup algorithm takes time $o(n)$. Thus if $1 ll k ll log n$ we get $o(nlog n)$ preprocessing time and $o(n)$ lookup time. For example, if $k = loglog n$ then preprocessing takes $O(nloglog n)$ and lookup takes $O(n/log n)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63700
