CODEWITHSUNDEEP
time-complexitycomputer-science
monkey
monkey

Reputation: 33

Time complexity of inner for loop

I have been trying to figure out how the get to the solution of this for loop but I cant seem to understand why the answer is what it is. I get stuck on the inner for loop, can someone help me break it down step by step and to get to the answer of the second for loop, line 2. THIS IS FOR REVIEW NOT HOMEWORK. I am just trying to understand the concept better.

 1: for (int i = 0; i < n; i++) { // Runs n+1 times
 2:     for (int j = n; j >= i; j--) { // Runs (n+2)+(n+1)+ n(n+1)/2 - 3 times
 3:         cout << i << “,” << j <<endl; // Runs (n+1) + n(n+1)/2 - 1 times
 4:     }
 5: }

I know the second line is simplified to n(n+1)/2 +2n, but I dont understand how to even get the (n+2)+(n+1)+ n(n+1)/2 - 3 first.

Upvotes: 0

Views: 79

Answers (2)

xycf7
xycf7

Reputation: 913

 1: for (int i = 0; i < n; i++) { // Runs n+1 times

This line does not run for n+1 times. Since it is i < n It runs for n times. 

2:     for (int j = n; j >= i; j--) {

This line runs for n - i + 1 times. Because it uses >= for comparison.

So if we write down the executions for cout , we get something like this:

1: n+1
2: n
3: n-1
...
...
n: 1

So what we need to do is simply add numbers up to n+1

which is (n+1)(n+2)/2

hope this helps

Upvotes: 1

Tony Tannous
Tony Tannous

Reputation: 14866

for (int i = 0; i < n; i++) { 
    for (int j = n; j >= i; j--) {
        cout << "something" << endl;
    }
}

Lets see for the values of i, how many times the inner loop is run.

i=0 --> n
i=1 --> n-1
i=2 --> n-2
i=3 --> n-3
...
...
i=n-1 --> 1

Let us increase each element to n to have an upper bound

1 + 2 + 3 +....+ n-1 + n < [n + n + n + .... + n] = O(n^2)

Lets throw half of the first elements, and the other half decrease it to n/2. For a lower bound.

1 + 2 + 3 +....+ n-1 + n > [n/2 + n/2 + ... + n/2] = (n/2)*(n/2) = (n^2)/4 = Ω(n^2)

Lower and Upper bounds are Ω(n), O(n), we can deduce it is actually ϴ(n).

We could have done this immediately by noticing it is actually an arithmetic sequence.

1 + 2 + 3 + ... + n = (1+n)*(n-1)/2 = ϴ(n^2)

Upvotes: 0

Related Questions