CODEWITHSUNDEEP
time-complexity
NANDAKUMAR THANGAVELU
NANDAKUMAR THANGAVELU

Reputation: 661

Compute Time Complexity

I got skunked in computing the time complexity in the inner loop.

Lets consider the following case.

Case 1:

for(int i = 0; i <= n; i++) - O(n)
{
    for(int j = 0; j <= i; j++)  - O(?);
    {
          //Some thing goes here
    }
}

Here the inner loop got executed every time up to value i.

So, can I tell like, the complexity for the inner loop is some O(i),

and the overall complexity is O(N) * O(I); ie: O(N*I)

Could some one explain in some brief manner, so i can able to understand the computing.

Thanks.

Upvotes: 1

Views: 76

Answers (2)

Naveen
Naveen

Reputation: 75

Before i go over what you asked for i will explain a simple example.
We caliculate the time complexity based on how many times the innermost loop is executed
consider this case:

for(i=0;i<n;i++){
    for(j=0;j<n;j++){
    ....
    }
}

here the outer loop is executed n times and in every iteration the inner loop is executed n times.
1st iteration - n
2st iteration - n
3st iteration - n
.
.
.
nth iteration -n
so the inner loop is executed n*n times.so it is O(n^2).
Now we caliculate for the case what you asked for

for(int i=0;i<=n;i++){
    for(int j=0;j<=i;j++){
      //Some thing goes here
    }
}

Here the Outer loop is executed for n times. and in every i'th iteration the inner loop is executed i times.
1st iteration - 1
2nd iteration - 2
3rd iteration - 3
.
.
.
nth iteration -n
so when we caliculate it would be
1+2+3+.....+n = n(n+1)/2
which is basically O(n^2). :)

Upvotes: 1

Benjamin Barenblat
Benjamin Barenblat

Reputation: 1311

The overall time complexity is O(n²) (in fact, it’s even Θ(n²)).

The inner loop has complexity O(i). However, n is related to i, so simply saying that the whole thing has complexity O(ni) is wrong. The body of the inner loop will run 0 + 1 + 2 + ⋯ + n = (n² + n) / 2 = Θ(n²) times.

Upvotes: 2

Related Questions