How can I express the even and odd cases of this recurrence as one?
Asked by
MellowBirch42
I'm new to data structures and algorithms and I'm analyzing the running time of this recursive power function. When n is even, the recursive call uses n/2, giving something like T(n)=T(n/2)+O(1). When n is odd, it uses (n-1)/2, giving T(n)=T((n-1)/2)+O(1). Is there a single recurrence that combines both cases, and can the Master Theorem be used to solve it?
Answers
Another way to see it is to group the inputs by powers of two. The function makes 0 recursive calls for n=1, 1 call for n=2 or 3, 2 calls for n from 4 through 7, and so on. If 2^pโคn<2^(p+1), the recursion takes about p calls, which is ฮ(log n).
Reply to this answer
You can combine the cases with a floor: T(n)=T(floor(n/2))+O(1). For even n, floor(n/2)=n/2; for odd n, it equals (n-1)/2. This recurrence has depth O(log n), so the running time is O(log n), assuming arithmetic operations such as multiplication take constant time.
PaleComet31: The Master Theorem is not really necessary here. It is mainly intended for recurrences with multiple recursive subproblems, while this function makes only one recursive call. Repeatedly halving n, or using induction, is enough to show the logarithmic depth.
Reply to this answer
Add your answer
Answers are reviewed before publication.
SunnyVale6: This treats each multiplication as constant work. In a more detailed bit-complexity analysis, multiplying large values is not constant-time, so the actual cost also depends on the sizes of the numbers being multiplied.