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?
2 Answers
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.
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).
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.
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.