1
$\begingroup$

The use of the phrase "worst-case running time" is really confusing to me. Isn't plainly stating that the time complexity of an algorithm is $O(n^2)$ supposed to mean that the growth rate of the algorithm is sub-quadratic? If it is then why do we say that $O(n^2)$ is the worst case time? Or do they have different meanings?

Thank you.

$\endgroup$
1
  • $\begingroup$ Worst-case means simply maximum, while best-case minimum and then we can say to which class of functions the given one belong. $\endgroup$
    – zkutch
    Mar 7 at 12:24
3
$\begingroup$

Suppose that you have an arbitrary array of $n$ numbers, and you give it to Quicksort to sort.

The expected running time of the algorithm is $O(n \log n)$. However, if the array is sorted, but in the wrong direction, and you pick the first element as pivot, then the algorithm might actually run in time $O(n^2)$.

That means that if you look at how Quicksort behaves with increasingly larger arrays of reversely sorted data, the time it uses grows as $n^2$.

However, if you spend $O(n)$ time to shuffle the array before sorting it, the expected running time is $O(n \log n)$; i.e. very few time will the algorithm spend close to $O(n^2)$ many operations.


A different example is with respect to amortized complexity. For example, adding a single element to an ArrayList in Java takes $O(1)$ time, most of the time. However, on a rare occasion, Java needs to create a new array and copy all the elements over to this new one. That takes $O(n)$ time.

This means that the worst case complexity for ArrayList.add is $O(n)$, but if you do this operation $n$ times, the total complexity is also $O(n)$, so we say that the amortized complexity is $O(1)$.

$\endgroup$
4
  • $\begingroup$ Thanks a lot, just one more question. What does it mean for a single input to run in $O(n^2)$? Isn't $O(n^2)$ related to the growth rate of the function and not the individual instances? For example we could say that Quicksort takes $n^2$ operations for some input instances, but I don't understand what is meant by a single instance taking $O(n^2)$. Thanks for the help. $\endgroup$
    – kasra
    Mar 7 at 13:08
  • 1
    $\begingroup$ @kasra You are right, a single instance doesn't have an asymptotic growth, that's why I said that if you look at the list of all reversely sorted lists, then you get $O(n^2)$. However, it makes it easier to talk about $O$-notation also when discussing single instances, but then it's always assumed that they are part of some infinite distribution. $\endgroup$
    – Pål GD
    Mar 7 at 13:51
  • $\begingroup$ Thanks you! Really appreciate it. $\endgroup$
    – kasra
    Mar 7 at 13:54
  • 1
    $\begingroup$ @PålGD When you explain the "the array is sorted in the wrong direction" part, I think it would be better to write $\Omega(n^2)$ or $\Theta(n^2)$ notation instead of $O(n^2)$. Since $O(n^2)$ also means that it could be $O(n)$. Just to be precise :P $\endgroup$ Mar 7 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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