CODEWITHSUNDEEP
c++big-o
Maria
Maria

Reputation: 45

calculating big O notation

sum = 0;
for (i=0;i<n/2;i++)
    for (j=i; j<n/4; j++)
        sum++;

What is the big O for the above code? I calculated the big O but I'm not sure if it's correct.

This is my answer

the outer loop will run n/2 times

the inner loop will run (n/4 - 1) = ((n-4)/4 )

T(n) = (n/2) * ((n-4)/4 )
     = (n^2 -4n + 16)/8
     = 1/8 n^2 - 1/2 n +2

so the big O is O(n^2) is this correct?

Upvotes: 1

Views: 311

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

The formal steps, using Sigma Notation, are like the following:

enter image description here

Upvotes: 1

Gnijuohz
Gnijuohz

Reputation: 3364

Well it is O(n^2) and if that's all you care(normally that should be) then you are right. But I don't think the constant is 1/8 though.

If you want to be precise I think it should be:

n/4 + n/4 -1 + n/4 - 2 + ... 3 + 2 + 1 = n/4 *(n/4 + 1)/2 = n^2/32 + n/8

When i is larger than or equal to n/4, the inner loop wouldn't run. So you shouldn't count that part in.

Upvotes: 1

TemplateRex
TemplateRex

Reputation: 70516

Yes, in big O computations leading coefficients and subleading terms are dropped.

The formal definition is that f(x) is O(g(x)) if f(x) <= M g(x) for x beyond some x0 and some constant M. In this case, M = 1/8 and x0 = 4.

Upvotes: 2

Crystal Meth
Crystal Meth

Reputation: 589

One very simple way of checking the big O of simple for loops that are nested within one another is this: O(n ^ (number of loops))

Note that the above technique is valid only if all the limits of the loop are real multiple of n.

In your question the inner loop is n/2 and outer loop is n/4. Both are real multiples of n. So the big O will be: O(n ^ 2).

Hope this helped.

Upvotes: 1

Related Questions