Determining the worst-case complexity of an algorithm

Question

Can someone please explain to me how one can determine the worst-case complexity of an algorithm. I know that the we need to use the equation W(n) = max{t(I)|I element of D), where D is the set of inputs of size n. Do I calculate the number of operations performed for each element I and then take its max? What easier way is there to accomplish this?

Answer 1

Starting from the equation is thinking of it a bit backwards. What you really care about is scalability, or, what is it going to do as you increase the size of the input.

If you just have a loop, for instance, you have a O(n) time complexity algorithm. If you have a loop within another loop though, it becomes O(n^2), because it must now do n^2 many things for any size n input.

When you are talking about worst case, you are usually talking about non deterministic algorithms, where you might have a loop that can stop prematurely. What you want to do for this is assume the worst and pretend the loop will stop as late as possible. So if we have:

for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(rand() > .5) j = n; } }

We would say that the worst-case is O(n^2). Even though we know that it is very likely that the middle loop will bust out early, we are looking for the worst possible performance.

Answer 2

That equation is more of a definition than an algorithm.

Does the algorithm in question care about anything other than the size of its input? If not then calculating W(n) is "easy".

If it does, try to come up with a pathological input. For example, with quicksort it might be fairly obvious that a sorted input is pathological, and you can do some counting to see that it takes O(n^2) steps. At that point you can either

1. Argue that your input is "maximally" pathological
2. Exhibit a matching upper bound on the runtime on any input

Example of #1:

Each pass of quicksort will put the pivot in the right place, and then recurse on the two parts. (handwave alert) The worst case is to have the rest of the array on one side of the pivot. A sorted input achieves this.

Example of #2:

Each pass of quicksort puts the pivot in the right place, so there are no more than O(n) passes. Each pass requires no more than O(n) work. As such, no input can cause quicksort to take more than O(n^2).

In this case #2 is a lot easier.