$O(n^2)$ running time vs $O(n^2)$ worst case

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.

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

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)$$.

• 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. Mar 7 at 13:08
• @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. Mar 7 at 13:51
• Thanks you! Really appreciate it. Mar 7 at 13:54
• @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 Mar 7 at 19:52