educative.io

Educative

Why do we add the time complexity of the inner loop instead of multiplying it?

I don’t understand why in this example we’re not multiplying the time complexity. Can somebody explain?


Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5724822843686912
Lesson: https://www.educative.io/collection/page/5642554087309312/5724822843686912/5684923537031168

Hi @pustelnikk. We don’t always add the time complexity of the inner loop. It depends. If the inner loop depends on the outer loop, then the complexity is added, and if the inner loop does not depend on the outer loop, then we multiply it.

Example 1:

for(int a=0;a<N;a++)
{
	for(int b=0;b<N;b++)
	{
	
	}

}

In this example, the inner loop is not dependent on the outer loop, so the time complexity will be O(N) * O(N) = O(N^2)

Outer loop complexity = O(N)
Inner loop complexity = O(N)

Example 2:

for(int a=0;a<n;a++)
{
	for(int b=a;b<n;b++)
	{
	
	}

}

In this example, the inner loop depends on the outer loop, so the time complexity will be N + N * (N–1)/2 ≈ N^2.

Outer loop complexity = O(N)
Inner loop complexity = N + N * (N–1)/2

2 Likes