6
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Patrick87 Mar 29 '14 at 13:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 6
    $\begingroup$ Your calculations are correct, but you misuse notation heavily. Don't forget that $O(f(n))$ denotes a class of function, you cant simply add the "big-Ohs". Try to work with upper bounding constants instead. $\endgroup$ – A.Schulz Oct 7 '13 at 8:21
  • $\begingroup$ Here is also a post: Can an $O(n)$ algorithm ever exceed $O(n^2)$ in terms of computation time? recently asked Q&A at SO. $\endgroup$ – Grijesh Chauhan Mar 29 '14 at 12:37
  • $\begingroup$ Well, $O(1) = O(2) = O(3) = \dots$ but, similarly, $O(n) = O(n/2) = O(n/3) = \dots$ -- so what's that summation of Landau terms supposed to mean? $\endgroup$ – Raphael Mar 29 '14 at 14:12
10
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

We have lots of questions about the time complexity of sums, and the answer is the same every time:

Loops translate to sums.¹

Every other shortcut will get you into trouble.

In your case, you seem to have identified statement1 as (dominant) operation you want to count. So your nested loop

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

translates quite literally to

$\qquad\displaystyle T(n) = \sum_{i=1}^{n-1} \sum_{j=1}^i c_1 = \sum_{i=1}^{n-1} i \cdot c_1 = c_1 \cdot \frac{(n-1)n}{2} \in \Theta(n^2)$.

Note the difference between $O$ and $\Theta$ and that you ignore the cost of maintaining the loop, i.e. initialising i resp. j, checking the condition and incrementing. Therefore, $T$ is not the real runtime function.

As an exercise, add the missing costs to above sum and evaluate it; does the result change? Why (not)?


  1. Disclaimer: Some algorithms don't lend themselves well to this translation, e.g. Dijkstra or even breadth-first-search. In these cases, other approaches work better.
$\endgroup$
3
$\begingroup$

You are thinking to much.. use a simpler model. Also as @A.Schulz pointed out, your calculations are correct in way, but there's some abuse of notation.

for(i=1;i < n;i++) {

. . . for(j=1;j<=i;j++){

. . . . . . statement1; } }

the first line (outer loop with $i$) takes $\theta(n)$ time, the second line (inner loop with $j$ ) also takes at-most $O(n)$ time.

So, the worst you could do is $\boxed{O(n^2) \text{ time}}$.

$\endgroup$
  • $\begingroup$ This is a dangerously rough strategy and prevents meaningful analysis of, say, Dijkstra's algorithm. $\endgroup$ – Raphael Oct 7 '13 at 14:54
  • $\begingroup$ @Raphael Yes, i agree (and thanks for pointing out Dijkstra), i actually wanted to emphasize this EXACT point when writing this, but I could not think of an example.. This is indeed a very coarse analysis with $O$ and not $\theta$. $\endgroup$ – Subhayan Oct 7 '13 at 15:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.