Time complexity for code patterns.

Time Complexity for code blocks

1- Two non-nested for Loop.

for (i = 0; i < N; i++) {
	// some logic
}
for (j = 0; j < M; j++) {
	// some logic
}

The time complexity for this code is O(N + M) because there are two loops, each iterating N and M times, respectively. The sum of these iterations gives the total number of iterations, which is O(N + M).

Space Complexity O(1) indicates that the algorithm does not use any additional space beyond the space required for the input and the variables used in the code.

Space Complexity O(1)

2- Nester for Loop

for (i = 0; i < N; i++) {
	for (j = N; j > i; j--) {
	    // some logic
	}
}

for (i = 0; i < N; i++) {
	for (j = i; j < M; j++) {
	        // some logic
	}
}

The time complexity for this code is O(N*N) because there are two nested loops, each iterating N times.

The outer loop runs N times, and for each iteration, the inner loop runs N times. Therefore, the total number of iterations is N * N.

3- Nester Loop variant

int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
	for (j = 2; j <= n; j = j * 2) {
		// some logic
	}
}

The outer loop runs from i = n / 2 to i = n, incrementing i by 1 in each iteration.

The outer loop runs a total of (n - n / 2 + 1) times.

The inner loop runs from j = 2 to j = n, doubling the value of j in each iteration.

The inner loop runs a total of (log2(n) + 1) times.

Time Complexity=Iterations of Outer Loop×Iterations of Inner Loop

Time Complexity=(n−n/2+1)×(log2(n)+1)

4 - While Loop Variant

int i = N;
while (i > 0) {
	// some logic
	i /= 2;
}

The loop runs until i becomes less than or equal to 0.

In each iteration, i is halved (i /= 2).

Number of Iterations=log2(N)

I hope you now understand the time complexity analysis for the provided code blocks.

For more such interesting learning you can connect with me by booking 1:1 strategy call for free.