Recurrence for Indicator Function

Question

Suppose you have a recursive function where:

I know the recurrence relation for the first if statement would be O(n) and the recurrence relation of the else condition would be O(logn). I am confused as to calculate the complexity of the entire function however. Would the overall complexity simply be O(n) since n dominates log(n)?

FYI log(n) isn't the same as lg(n). log is base 10, while lg is base 2. When you're recursively calling foo(x/2) you're really doing lg(n) — Boundless, Feb 11 '13 at 01:30

score 1 · Accepted Answer · edited May 23 '17 at 11:48

1

By definition, big O is the upper bound, so it would be O(n) (since O(n) is greater than O(lg(n)). Read a little about big O and big theta Big-oh vs big-theta

EDIT:

Assuming that the code would look something like:

foo(x,y)
{
 if(y<0):
  //call some other function, or throw an error, otherwise we're stuck in an infinite loop
 else if(y==0):
   return 1
 else if(y%2!=0):
   return x*foo(x,y-1)
 else:
   return foo(x,y/2)*foo(x,y/2)
}

Here, Big O is O(n), but technically speaking it would also be O(n^2), O(n^3), etc. This is because Big O is an upper bound.

Big Theta (the tight bound) is Theta(n).

Note that just because you may reduce y by dividing y/2, you don't reduce the calls to foo, since you are doing twice as many: foo*foo. Since you double your function calls, you don't get a performance of Theta(lg(n)).

edited May 23 '17 at 11:48

Community

1
1

answered Feb 11 '13 at 01:27

Boundless

2,444
2
25
40

How would I express this in theta notation? Would it just be theta(n)? – phil12 Feb 11 '13 at 01:51
I'll help you figure that out if you fix your code. First you have foo(x,y) *notice that it takes 2 variables. Then you call foo(x-1) or foo(x/2) *notice that you're only sending one variable. Second, your code can cause an infinite loop, because y is never changed. I'm assuming that y is a typo, and the function should be just foo(x), and the first condition should be if(x==0)... If this is the case you still have a problem with your code being infinite, given the case that x starts off negative. – Boundless Feb 11 '13 at 01:57

score 0 · Answer 2 · answered Feb 11 '13 at 01:24

0

I believe you can break it down into O(n) being worst case and O(logn) being the best case.

Just giving some ideas, this by all means is not a complete answer.

answered Feb 11 '13 at 01:24

Dmytro

5,068
4
39
50

Recurrence for Indicator Function

2 Answers2