# What is the asymptotic runtime of this nested loop? [duplicate]

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?

## marked as duplicate by Patrick87Mar 29 '14 at 13:23

• 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. – A.Schulz Oct 7 '13 at 8:21
• 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. – Grijesh Chauhan Mar 29 '14 at 12:37
• 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? – Raphael Mar 29 '14 at 14:12

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$.