CODEWITHSUNDEEP
algorithmbig-oasymptotic-complexity
David West
David West

Reputation: 562

Algorithm Analysis: Big-O explanation

I'm currently taking a class in algorithms. The following is a question I got wrong from a quiz: Basically, we have to indicate the worst case running time in Big O notation:

int foo(int n) 
 {
    m = 0;
   while (n >=2)
   {
    n = n/4;
    m = m + 1;
   }   
   return m;
 }

I don't understand how the worst case time for this just isn't O(n). Would appreciate an explanation. Thanks.

Upvotes: 0

Views: 105

Answers (3)

AlienRancher
AlienRancher

Reputation: 639

The computation can be expressed as a recurrence formula:

f(r) = 4*f(r+1)

The solution is 

f(r) = k * 4 ^(1-r)

Where ^ means exponent. In our case we can say f(0) = n

So f(r) = n * 4^(-r)

Solving for r on the end condition we have: 2 = n * 4^(-r)

Using log in both sides, log(2) = log(n) - r* log(4) we can see

r =  P * log(n);

Not having more branches or inner loops, and assuming division and addition are O(1) we can confidently say the algorithm, runs P * log(n) steps therefore is a O((log(n)).

http://www.wolframalpha.com/input/?i=f%28r%2B1%29+%3D+f%28r%29%2F4%2C+f%280%29+%3D+n

Nitpickers corner: A C int usually means the largest value is 2^32 - 1 so in practice it means only max 15 iterations, which is of course O(1). But I think your teacher really means O(log(n)).

Upvotes: 0

Jean Catanho
Jean Catanho

Reputation: 326

Let's suppose that the worst case is O(n). That implies that the function takes at least n steps.

Now let's see the loop, n is being divided by 4 (or 2²) at each step. So, in the first iteration n is reduced to n/4, in the second, to n/8. It isn't being reduced linearly. It's being reduced by a power of two so, in the worst case, it's running time is O(log n).

Upvotes: 1

perreal
perreal

Reputation: 98118

foo calculates log4(n) by dividing n by 4 and counting number of 4's in n using m as a counter. At the end, m is going to be the number of 4's in n. So it is linear in the final value of m, which is equal to log base 4 of n. The algorithm is then O(logn), which is also O(n).

Upvotes: 2

Related Questions