6
$\begingroup$

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(n\log(n))$.

As far as I know, you can not sort an array in less than $O(n\log(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(n\log(n))$ such that a lookup algorithm can do a search faster than $O(n)$, though not as fast as $O(\log(n))$?

$\endgroup$
9
  • $\begingroup$ I am aware that there may be a very basic error or misconception in there somewhere, I am not and have never studied computer science, and I am not comfortable with the $O$ notation. $\endgroup$ Sep 20, 2016 at 21:12
  • 2
    $\begingroup$ You can sort a list in $O(n\log n)$ time. $\endgroup$ Sep 20, 2016 at 21:19
  • 1
    $\begingroup$ It is a bit unclear what exactly you are looking for, but take a quicksort - median pivoted version (guaranteed to work in nlogn in exchange for median overhead. Now take half of the steps. What that gives you? Data is partitioned, and in the every partition elements are not far from the sorted index but during lookup you have to traverse a partition. $\endgroup$
    – Evil
    Sep 20, 2016 at 22:05
  • 2
    $\begingroup$ Please define what exactly you mean by "partially sorted". There are many competing notions of sortedness in the literature. $\endgroup$
    – Raphael
    Sep 20, 2016 at 23:21
  • 1
    $\begingroup$ "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)" Maybe. "Can partial sorting help with lookup cost in arrays?" Absolutely not (for a single lookup). $\endgroup$ Sep 21, 2016 at 1:17

1 Answer 1

12
$\begingroup$

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(n\log n)$. If $k = \omega(1)$ then the lookup algorithm takes time $o(n)$. Thus if $1 \ll k \ll \log n$ we get $o(n\log n)$ preprocessing time and $o(n)$ lookup time. For example, if $k = \log\log n$ then preprocessing takes $O(n\log\log n)$ and lookup takes $O(n/\log n)$.

$\endgroup$
2
  • 2
    $\begingroup$ If the balanced quicksort knows the target value, and only recurses on the side with the target value, then the time is ~4n to go the full depth. This is how C++'s std::partial_sort is implemented. $\endgroup$ Sep 21, 2016 at 1:21
  • $\begingroup$ An alternative is incomplete radix sorting. The preprocessing time can be faster, but there is less control over the bucket sizes. A similar comment can be made about prefix perfect hashing. $\endgroup$ Sep 21, 2016 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.