# Time complexity of for loop – O(1) O(n) and O(log n)

Time complexity of for loop can be anything O(1), O(n), O(log n) depending upon the loop conditions and code you write.

## Time complexity of for loop with various scenarios.

a)

``````	int sum = 0;
for (int x = 0; x < 10; x++) {
sum = sum +x;
}
``````

Every time you run this loop; it will run 10 times. In other word, this for loop takes constant time. So, the time complexity will be constant O (1).

b)

``````	int sum = 0;
for (int x = 0; x < n; x++) {
sum = sum +x;
}
``````

The time complexity of this for loop would be O (n) because the number of iterations is varying with the value of n.

c)

``````	for (int x = 1; x <= n; ) {
x = x * 2;
}
``````

In this for loop, notice that in every iteration, the value of x is getting doubled as shown below. At the nth iteration, the value of x would be 2k.

``````Iteration |   x
-----------------
0     |   20     // = 1
1     |  21      // = 2
2     |  22      // = 4
3     |  23      // = 8

...     |  ...
...     |  ...
n     |  2k

So, we can represent it as
2k   = n
Apply algorithms at both sides considering base 2
=> log 2k = log n // base 2
=> k = log ( n) .
``````

## Nested for loop time complexity

``````	int sum = 0;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++)
sum = sum +x+y;
}
``````

This nested loop will have time complexity as O(n^2). Because the outer for loop will run n times and for each iteration, the inner for loop will also run for n times.

So, O(n)*O(n) = O(n^2)