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 2^k.

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)

READ MORE:

BIG-O NOTATIONS

Time Complexity of linear search