# 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
-----------------
1st     |  2 -> 2^1 ( 2 the power 1)
2nd     |  4 -> 2^2
3rd     |  8 -> 2^3
4th     |  16-> 2^4

...     |  ...-> ...
...     |  ...-> ...
nth    |  ...-> 2^k

So, we can represent it as
2^k   = n
Apply algorithms at both sides considering base 2
=> log 2^k = log n // base 2
( You know that value of log 2^k on base 2 will be the power value i.e. k)
=> 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)