CODEWITHSUNDEEP
c++
user2843556
user2843556

Reputation: 1

Running time of nested for loop

Running time for following alorithm

int b = 0;
for (i = 0; i < n; i++) 
    for (j = 0; j < i * n; j++)   
        b = b + 5;

I know that the first loop is O(n) but that's about as far as I've gotten. I think that the second loop may be O(n^2) but the more I think about it the less sense it makes. Any guidance would be much appreciated.

Upvotes: 0

Views: 138

Answers (4)

P0W
P0W

Reputation: 47784

     Statements                                     Iterations
for (i = 0; i < n; i++)           |       n+1
    for (j = 0; j < i * n; j++)   |       0+n+2n+3n...n*n = n*n(n+1)/2
        b = b + 5;                |       n*n(n+1)/2

So overall: O(n3)

Upvotes: 1

Manoj Awasthi
Manoj Awasthi

Reputation: 3520

Outer loop runs for n iterations.

When n is 0, inner loop executes 0*n = 0 times When n is 1, inner loop executes 1*n = n times When n is 2, inner loop executes 2*n = 2n times When n is 3, inner loop executes 3*n = 3n times ... ... When n is n, inner loop executes n*n = n*n times

So it looks like inner loop executes a total of: 

0 + n + 2n + 3n + ... + n*n

Multiply this with outer loop's n and you get approx. a O(n^3) complexity.

Upvotes: 1

Kaushik Sivakumar
Kaushik Sivakumar

Reputation: 205

easiest way would be to use a example

assume n=10 

1st for loop runs 10 times o(n)
2nd loop loop runs 0 if i=0
                   10 time for i=1
                   20 times for i=2
                   30 times for i=3
....  100 times(for i=10) o(n^2)

hope it helps you

Upvotes: 1

alecbz
alecbz

Reputation: 6488

We want to express the running time of this code as a function of n. Call this T(n).

We can say that T(n) = U(0,n) + U(1,n) + ... + U(n-1,n), where U(i,n) is the running time of the inner loop as a function of i and n.

The inner loop will run i * n times. So U(i,n) is just i * n.

So we get that T(n) = 0*n + 1*n + 2*n + ... + (n-1)*n = n * (1 + 2 + ... + (n-1)).

The closed form for (1 + 2 + ... + (n-1)) is just (n^2 - n)/2 http://www.wolframalpha.com/input/?i=1+%2B+2+%2B+...+%2B+(n-1) .

So we get that T(n) = n * (1 + 2 + ... + (n-1)) = n * ((n^2 - n)/2) = (n^3 - n^2) / 2,

which is O(n^3).

Upvotes: 1

Related Questions