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