Analyzing the worst-case runtime of an algorithm

The setup

Let $\mathcal{A}$ be the algorithm we are trying to analyze. Then we will define $T(N)$ to be the worst-case run-time of $\mathcal{A}$ over all inputs of size $N$. Slightly more formally, let $t_{\mathcal{A}}(\mathbf{x})$ be the number of steps taken by the algorithm $\mathcal{A}$ on input $\mathbf{x}$. Then \[T(N)=\max_{\mathbf{x}: \mathbf{x}\text{ is of size } N} t_{\mathcal{A}}(\mathbf{x}).\]

In this note, we present two useful strategies to prove statements like $T(N)$ is $O(g(N))$ or $T(N)$ is $\Omega(h(N))$. Then we will analyze the run time of a very simple algorithm.

Preliminaries

We now collect two properties of asymptotic notation that we will need in this note (we saw these in class today).

Proving $T(N)$ is $O(f(N))$

We start off with an analogy. Say you wanted prove that given $m$ numbers $a_1,\dots,a_m$, $\max_i a_i\le U$. Then how would you go about doing so? One way is to argue that the maximum value is attained at $i^*$ and then show that $a_{i^*}\le U$. Now this is a perfectly valid way to prove the inequality we are after but note that you will also have to prove that the maximum value is attained at $i^*$. Generally, this is a non-trivial task. However, consider the following strategy:

Let us consider an example to illustrate the two strategies above. Let us say for whatever reason we are interested in showing that the age of the oldest person in 331 lectures is at most $100$. Since there are $141$ students registered and I am always present in class, there are at most $m=142$ folks in the class. Let us order them somehow and let $A_i$ denote the age of the $i$'th person. Then we want to show that $\max\{a_1,\dots,a_{142}\}\le 100$ (i.e. $U=100$). The first strategy above would be to first figure out who is the oldest person in room: say that is the $i^*$'th person (where $1\le i^*\le 142$) and then check if $a_{i^*}\le 100$. However, this strategy is somewhat invasive: e.g. the oldest person might not want to reveal that they are the oldest person in the room. This is where the second strategy works better: we ask every person in the room if their age is $\le 100$: i.e. we check if for every $1\le i\le 142$, $a_i\le 100$. If everyone says yes, then we have proved that $\max_i a_i\le 100$ (without revealing the identity of the oldest person).

Mathematically the above two strategies are the same. However, in "practice," using the second strategy turns out to be much easier. (E.g. this was true in the age example above.) Thus, here is the strategy to prove that $T(N)$ is $O(f(N))$:

Proving $T(N)$ is $\Omega(f(N))$

We start off with the same analogy as in the previous section. Say you wanted prove that given $m$ numbers $a_1,\dots,a_m$, $\max_i a_i\ge L$. Then how would you go about doing so? Again, one way is to argue that the maximum value is attained at $i^*$ and then show that $a_{i^*}\ge L$. Now this is a perfectly valid way to prove the inequality we are after but note that you will also have to prove that the maximum value is attained at $i^*$. Generally, this is a non-trivial task. However, consider the following strategy:

Let us go back to the class room example. Now let us say we are interesting in proving that the oldest person in the room is at least $25$ years old. (So $a_1,\dots,a_m$ is as in previous example but now $L=25$.) Again, the first strategy would be to first figure out the oldest person, say $i^*$ and check if $a_{i^*}\ge 25$. However, as we saw earlier, this strategy is somewhat invasive. However, consider the the following implementation of the second strategy above. Say for the sake of mathematics, I come forward and volunteer the information that my age is at least $25$. Since the oldest person's age has to be at least mine, this proves that $\max_i a_i\ge 25$, as desired.

Mathematically the above two strategies are the same. However, in "practice," using the strategy second turns out to be much easier. (E.g., this was true in the age example above.) Thus, here is the strategy to prove that $T(N)$ is $\Omega(f(N))$:

An Example

Now let us use the big-Oh and big-Omega strategies from above to asymptotically bound the run-time of a simple algorithm. Consider the following simple problem:

Below is a simple algorithm to solve this problem (which I'm sure you have seen/used before).

					//Input: A[0],...,A[n-1];v

					for(i=0; i< n; i++)
    						if(A[i]==v)
         						return i;
					return -1;
				

We will prove Theorem 1 by proving Lemmas 1 and 2 below.

A quick remark on the proof of Lemma 2. Since by the big-Omega strategy, we only need to exhibit only one input with runtime $\Omega(n)$, the input instance in the proof above is only one possibility. One can choose other instances: e.g. we can choose an instance where the output has to be $-1$ (as a specific instance consider $a_i=i$ and $v=0$). For this instance one can make a similar argument as in the proof above to show that $T(n)\ge \Omega(n)$.

If you think you need more examples to work through to make yourself comfortable with analyzing $T(n)$ for different algorithms,

The Best-Case Input "Trap"

We now briefly talk about a common mistake that is made when one starts trying to prove $\Omega(\cdot)$ on $T(N)$. Note that the big-Omega strategy says that one can prove that $T(N)$ to be $\Omega(f(N))$ for every large enough $N$, one only needs to pick one input of size $N$ for which the algorithm takes $\Omega(f(N))$ steps.

The confusing part about the big-Omega strategy is how does one get a hand on that special input that will prove the $\Omega(f(N))$ bound. There is no mechanical way of finding this input. Generally, speaking you have to look at the algorithm and get a feel for what input might force the algorithm to spend a lot of time. Sometimes, the analysis of the $O(\cdot)$ bound itself gives gives us a clue.

However, one way of picking the ``special" input that almost always never works in practice is to consider (for every large enough $N$), the ``best-case input," i.e. an input of size $N$ on which the algorithm runs very fast. Now such an input will give you a valid lower bound but it would almost never give you a tight lower bound.

So for example, let us try to prove Lemma 2 using the best case input. Here is one best case input: $a_i=i$ for every $i\in [n]$ and $v=1$. Note that in this case the algorithm finds a match in the first iteration and this terminates in constant many steps. Thus, this will prove an $\Omega(1)$ lower bound but that is not tight/good enough. As mentioned earlier, this is not an uncommon "mistake." E.g. below is a video¹ from CS 50 at Harvard that uses the best-case input strategy to prove $\Omega(\cdot)$ bounds on some algorithms: