# How can you have an upper and lower bound on the worst-case complexity of an algorithm?

Yesterday I started reading "An Introduction To The Analysis of Algorithms" by Sedgewick/Flajolet. For me it was not clear what he meant with "theory of algorithms" and the "scientific approach". I googled a bit and found someone who had the same question:

Sedgewick analysis of algorithm, difference between theory of algorithm and scientific approach

Until then I thought that I had a good understanding of what worst-case complexity of an algorithm is and how it relates to $$O()$$ but I think that I was a bit wrong.

In the upper thread someone commented: "(BTW O(), Ω(), Θ() as used in CLRS are about upper, lower and tight bounds all on the worst-case running time, they are not about worst-case, best-case, average-case.)"

And then I was confused. Let split this up in worst-case analysis of a problem and worst-case analysis of a specific algorithm.

Worst-case analysis of a problem

When you have a problem B you want to solve, than it is absolutely understandable that you can have an upper and lower bound on the worst-case complexity since there are numerous algorithms for problem B which all can have different worst-case complexities.

In this case one could say:

The worst-case complexity of problem B lies in O(f(n)) if there is an algorithm for problem B whose worst-case runtine complexity lies in O(f(n)).

The worst-case complexity of a problem B lies in Ω(f(n)) if there can't be (yeah this has to be rigorously proved) an algorithm for the problem B whose worst case complexity lies not! in Ω(f(n)).

A good example is the proof in CLRS that the worst-case complexity of sorting(via comparing) lies in Θ(n log(n)).

So now to the worst-case complexity of an algorithm.

Worst-case analysis of an algorithm

Lets say we have an algorithm A for some problem and want to find out something about the worst-case complexity of A. For the upper bound I just have to find out for which problem instances the algorithm A has to do the most steps or the most "work".

So here is my problem: What should the lower bound on the worst-case complexity of an algorithm A be?

There is only one way which for me could explain that. If every algorithm yields several different implementations than one could really define a lower bound on the "best" worst-case complexity on all possible implementations of this algorithm A.

If everything what I wrote here is right for the most part than I have to say, that a lot! of books deal extremely sloppy with the relation between the asymptotic analysis and the best-,average and worst-case runtime.

There is no real difference between the definition of upper and lower bounds.

You say

For the upper bound I just have to find out for which problem instances the algorithm A has to do the most steps or the most "work"

Well, that is the same thing with the lower bound, but instead of saying "this particular worst instance of size $$n$$ takes at most $$f(n)$$ time to compute", you will say "this particular worst instance of size $$n$$ takes at least $$g(n)$$ time to compute".

Obviously, since we are talking about the same worst instance, the computing time will be the same, so it would be more pertinent to give a tight bound instead of a lower or an upper. However, it is not always as easy to find a lower bound than an upper bound (and vice versa).

For example, considering the quicksort algorithm, the worst-case occurs when the array is already sorted. Since a partition is needed, it is easy to see that the worst-case is $$\Omega(n)$$. Since there is at most $$n$$ calls to the partition function, we can say that the worst-case is $$\mathcal{O}(n^2)$$. However, it needs a bit more of analysis to conclude that the worst-case is $$\Theta(n^2)$$.

• “Quadratic” is worst case for naive Quicksort. No serious implementation will take quadratic time for an already sorted array. Many will take linear time. Nov 14 at 17:44
• @gnasher729 Any reasonnable implementation of Quicksort will still have a worst-case in $\mathcal{O}(n^2)$, even with random or median-of-three selection of pivot. A selection of pivot with the median of medians can improve the worst-case bound, but as noted here, it is significantly worse in practice. Nov 14 at 17:54
• Obviously, I wanted to say a worst-case in $\Theta(n^2)$. Nov 14 at 18:02
• Ok, now I think that I know what my problem was. So it is right, that for every algorithm A obviously there is a function $f(n)$, so that the worst case complexity of A lies in $\Theta(f(n))$. But in reality it is not that easy to find out when an algorithm is making the most steps or what this worst case instance should be (I actually thought that it shouldn't be that hard to find such a worst case instance). Am I right? Nov 14 at 18:39

Just because an algorithm has a worst case, doesn’t mean you can find it out.

You may find a set of cases that seem quite bad to you, but can all be solved in O(n^2). But you can’t prove that every instance can be solved in O(n^2). So the lower bound for worst case is O(n^2). On the other hand maybe you can prove that every instance can be solved in O(n^3). But you don’t actually have a set of instances that take that long. The worst you have is your set of O(n^2) instances. So you have an upper bound for the worst case, which is O(n^3). The actual worst case is somewhere in between.