I need to calculate the time complexity of the following code:
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
// Some code
}
}
Is it O(n^2)?
This question is related to
big-o
complexity-theory
time-complexity
First we'll consider loops where the number of iterations of the inner loop is independent of the value of the outer loop's index. For example:
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
sequence of statements
}
}
The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the total complexity for the two loops is O(N2).
Yes, the time complexity of this is O(n^2).
On the 1st iteration of the outer loop (i = 1), the inner loop will iterate 1 times
On the 2nd iteration of the outer loop (i = 2), the inner loop will iterate 2 time
On the 3rd iteration of the outer loop (i = 3), the inner loop will iterate 3 times
.
.
On the FINAL iteration of the outer loop (i = n), the inner loop will
iterate n times
So, the total number of times the statements in the inner loop will be executed will be equal to the sum of the integers from 1 to n, which is:
((n)*n) / 2 = (n^2)/2 = O(n^2) times
A quick way to explain this is to visualize it.
if both i and j are from 0 to N, it's easy to see O(N^2)
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
in this case, it's:
O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O
This comes out to be 1/2 of N^2, which is still O(N^2)
Indeed, it is O(n^2). See also a very similar example with the same runtime here.
Source: Stackoverflow.com