current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

I am working on figuring out big O notation for algorithms and I was wondering if I have this down correctly.

I am currently analyzing the following code:

int expon(int x, int n) /* n > 0 */
{   
  if (n==0) return 1;
  else
  {
    if even(n) return expon(x*x, n/2);
    else
      return expon(x, n-1)*x;
  }
}

This is what I have so far: The first if statement where it checks to see if n = 0 is simply a constant all it gets is c.

The second if statement where the even(n) check is called does this n times, thus receiving an n and the return expon(x*x, n/2) does this n amount of times also receiving an n. So that if statement is n^2. The final statement where it handles everything else only executes once, so we can call that c.

Finally we add this all up and we get: c+c(n^2). And if we want to write this in bigO notation, we would drop the constants and simply write O(n^2).

Could anyone correct me if I am wrong here? I feel like I am not analyzing this correctly (especially the second if) as well as not adding/multiplying the n's and c's total correctly.

Thanks a bunch!

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Let's look at this in a different way: the runtime of the algorithm is determined by n, the value of x only influences the value that you get at the end. So let's see what happens to n: the value of n either goes down by 1 or it gets halved in a recursive call.

If n is even then we divide by two and perform the recursive call.

If n is odd then we subtract one and then it becomes even again. So for odd numbers we perform one additional call to make the number even.

So we can observe that n goes down by one or is halved (alternatingly). That pattern is O(log n). If we double n then we'd only need one or two more recursive calls to finish the algorithm, which is what O(log n) expresses. If it were O(n^2) then increasing n by one would increase the runtime of the algorithm by a lot more.

share|improve this answer
    
I would say that worst case for total number of iterations are about O(logN + logN) = O(2 * logN), as soon as we're omitting consts from big O - O(logN) –  Lashane Feb 9 at 2:02
    
Thank you so much! @Lashane You cleared things up for me entirely! –  Nick Feb 9 at 2:14
add comment
up vote 1 down vote

The approach you're using looks mostly correct. However, the order of magnitude is O(log n). O(n^2) increases by an increasing factor as n increases; this increases by a decreasing factor as n increases. For example, when n is 2, 4 and 8, the loop is run through 1, 2 and 3 times.

The problem with your implementation is that it needs:

else if (n == 1) return x;
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.