What is the asymptotic runtime of this nested loop?

Answered By : Gilles

The result is correct, but your reasoning is not. You can't mix big-oh with ellipses. It happens to work here because of extra conditions that happen to be true but that you haven't checked.

Why summing big-ohs just doesn't work

Fundamentally, you are abusing notation. For example, it doesn't make much sense to write $O(1)$, $O(2)$, $O(3)$, etc. as if they were different things — after all, they all mean "bounded function".

The definition of big-oh depends on some values that differ from one $O(…)$ to the next. When you write $O(1) + \ldots + O(n)$, the constants could be different in each term of the sum, and if they are, you can't say anything about the sum. $f(n) = O(g(n))$ means that there exists some threshold $N$ and some factor $C$ such that if $n \ge N$ then $f(n) \le C g(n)$. When you have a variable number of big-ohs like $O(f_1) + \ldots + O(f_n)$, each term of the sum has its own threshold and factor. Your reasoning assumes that the threshold and factor are the same, and it's true that in this example you can pick them to be the same, but it isn't true in general.

The first hurdle is what $O(1) + \ldots + O(n)$ actually means. This is a sum whose general term is $O(k)$: $O(1) + \ldots + O(n) = \sum_{k=1}^n O(k)$. The general term of the sum could depend on both $k$ (the index into the sum) and $n$ (the number of terms)! Big-oh is defined in terms of a variable, it describes what happens when that variable approaches infinity. If you consider the general term as a function of $k$, then $O(k)$ means that there exists some threshold $K_n$ and some factor $D_n$ such that if $k \ge K_n$ then $f_k(n) \le D_n k$. If you consider the general term as a function of $n$, then $O(k)$ means that the function is bounded for any given $k$, i.e. that there exists a bound $B$ such that $\forall n, f_k(n) \le B_k$.

To illustrate how the sum can get big under the first interpretation, consider the function $$ f'_k(n) = 2^n k $$ For any given $n$, $f'_k(n) \le D_n k$ where $D_n = 2^n$ so $f'_k(n) = O(k)$ as a function of $k$. Yet the sum is $$ \sum_{k=1}^n f'_k(n) = f'_1(n) + \ldots + f'_n(n) = 2^n \cdot 1 + 2^n \cdot 2 \ldots + 2^n \cdot n = 2^n \cdot (1 + 2 + \ldots + n) = 2^n \frac{n(n+1)}{2}$$ which is not $O(n^2).

To illustrate how the sum can get big under the second interpretation, consider the function $$ f''_k(n) = k^2 $$ The general term $f''_k(n)$ is constant with respect to $n$, so it is $O(k)$ as $n$ goes to infinity (since $k$ is fixed, this is the same as writing $O(1)$). Yet the sum is $$ \sum_{k=1}^n f''_k(n) = f''_1(n) + \ldots + f''_n(n) = 1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6} $$ which is not $O(n^2)$.

What actually works

Here, you have a special case which does make sense. It's not any sum of big-ohs — it's the same function every time: $$ f(1) + f(2) + \ldots + f(n) = \sum_{k=1}^n f(k) $$ where $f(k) = O(k)$. Now we have a function of a single variable, which makes the analysis simpler. By the definition of big-oh, there is a threshold $N$ and a factor $C$ such that for all $k \ge N$, $f(k) \le C k$. Therefore, if $n \ge N$, then $$ \sum_{k=1}^n f(k) = \sum_{k=1}^{N-1} f(k) + \sum_{k=N}^n f(k) \le \sum_{k=1}^{N-1} f(k) + \sum_{k=N}^n C k \le \sum_{k=1}^{N-1} f(k) + C \frac{n(n+1) - N(N-1)}{2} $$ This last term is of the form $C n^2 + B n + A$, so it is $O(n^2)$ and thus $\sum_{k=1}^n f(k) = O(n^2)$.

If $f$ is monotonically increasing (which is often but not always the case for complexity bounds), then there is an easier way to prove this: $$ \sum_{k=1}^n f(k) \le \sum_{k=1}^n f(n) = n f(n) $$ and since $f(n) = O(n)$, the sum is $O(n \cdot n) = O(n^2)$.

Note that we are taking the sum of the values of a function which is $O(n)$. This is crucially different from summing functions, each of which is $O(n)$.

Application to a loop

Consider a loop

for i = 1 to n do     /*do something*/ 

If the running time of /*do something*/ does not depend on $n$, then we are in the case that works. For example, take your nested loop:

for i = 1 to n do     for j = 1 to i do         statement 

Assuming that statement runs in constant time, the run time of the inner loop is $j$ which is $O(j)$. The run time of the outer loop is thus $O(n^2)$. Of course, you don't need to remark that $j = O(j)$ to see this — you could directly remark that $j \le n$ and therefore statement is executed at most $n$ times per run of the inner loop and thus at most $n^2$ times per run of the outer loop.

The general way to analyze the complexity of loops is by summing the complexity of the iterations. You cannot sum big-ohs, you need to write an actual mathematical expression. If the final desired result is a big-oh approximation, then you don't need to write an exact computation: it is enough to find an upper bound for each term and then calculate an upper bound for the sum of the upper bounds.

Problem Detail: 

I am trying to analyse the runtime of this algorithm:

for(i=1; i < n; i++){    for(j=1; j <= i; j++){          statement1;    }        } 

Expanding the above loop into.

• First :

  for(j=1; j <= 1; j++){    statement1;          //complexity O(1) } 

• Second:

  for(j=1; j <=2 ; j++){    statement1;          //complexity O(2) }        

...

• n-th:

  for(j=1; j <= n; j++){    statement1;          //complexity O(n) } 

So the runtime of the loop should be

$\qquad \displaystyle O(1) + \dots + O(n) = O\Bigl(\frac{n(n+1)}{2}\Bigr) = O(n^2)$.

Can I reason like this, or what is the proper way to analyse nested for-loops?

Asked By : Shravan40

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14880