CODEWITHSUNDEEP
algorithmtime-complexitynested-loops
ravsmy
ravsmy

Reputation: 37

How to do this nested for loop time complexity?

I'm trying to figure out this time complexity:

for(i=0; i<=(n/2)-1; i++){
    for (j=i+1; j<=(n/2)-1; j++){
        --some O(1) thing--                
    }   
}

The outer loop I understand to be on its own O(n/2.) However with the inner loop as well I can't wrap my brain around how to break down how many times O(1) executes.

If the inner one stared j=0 I could do n/2(inner) * n/2(outer) = O(n^2) time complexity right? However since j depends on i, I'm thinking some type of summation is involved from i+1 to n/2 but i can't figure out how to set it up...

Basically I need help kind of visualizing how many times it loops, and how to set the summation up. Thank you! :)

Upvotes: 1

Views: 823

Answers (2)

Zabuzard
Zabuzard

Reputation: 25903

Premise

For simplicity, let us call m = n / 2 - 1. The outer loop runs from 0 to m. The inner loop from i + 1 to m.

Iteration counting

We need to count how often the inner statement which you labeled O(1) is executed. That is, how often the inner loop runs in total, as executed by the outer loop. So let us take a look.

The first iteration of the outer loop generates m - 1 iterations of the inner loop. The second generates m - 1, then m - 2, m - 3, m - 4, ..., 2, 1, 0.

That means that the O(1) statement is, in total, executed:

(m - 1) + (m - 2) + (m - 3) + ... + 2 + 1 + 0

That is the sum from 0 up to m - 1

sum_{i = 0}^{m - 1} i

which can be simplified to

(m^2 - m) / 2

Substitute back

Let us now substitute back m = n / 2 - 1, we get

((n / 2 - 1)^2 - (n / 2 - 1)) / 2

After simplifying, this is

n^2/8 - 3n/4 + 1

Big-O

For Big-O, we observe that it is smaller than

  n^2 - 0 + n^2
= 2n^2

Which, by definition is O(n^2).

As you see, this bound is also tight. So we also receive Omega(n^2) which also concludes Theta(n^2).

Upvotes: 2

Che Huu
Che Huu

Reputation: 163

Assuming that m = n/2. You will see that in inner loop, j will iterater over range m-1, m-2, m-3,... 1. Summing all of that will be 1+2+..+m-1 = (m-1)*m/2 = O(m^2)

Upvotes: 2

Related Questions