How can I combine the even and odd cases into one recurrence?
Asked by
MellowBirch42
I'm new to data structures and algorithms and am analyzing the running time of this exponentiation function. When n is even, it makes one recursive call with n/2; when n is odd, it makes one recursive call with (n-1)/2. That gives recurrences like T(n)=T(n/2)+O(1) and T(n)=T((n-1)/2)+O(1). Can these cases be represented with a single recurrence, and is the Master Theorem appropriate here?
Answers
Another way to describe it is by ranges: the recursion takes about p calls whenever 2^p ≤ n < 2^(p+1). Each call reduces the exponent by roughly half, so the number of calls is proportional to log n. The exact odd/even distinction does not change the asymptotic result.
Reply to this answer
You can combine both branches as T(floor(n/2))+O(1). For even n, floor(n/2)=n/2, and for odd n, floor(n/2)=(n-1)/2. Since floor(n/2) is at most n/2, the recursion depth is logarithmic, so the running time is O(log n) if multiplication is treated as constant-time.
VelvetOrbit3: The Master Theorem usually applies to recurrences with multiple subproblems, such as 2T(n/2)+O(1). Here there is only one recursive call, so directly observing that n is roughly halved at every step—or using induction—is more appropriate.
Reply to this answer
Add your answer
Answers are reviewed before publication.
SilverKite26: This assumes each multiplication is constant cost. With arbitrarily large values of x and n, multiplication itself can take more than constant time depending on the number of bits, so a more detailed bit-complexity analysis would account for that.