Thread: Asymptotic Analysis of Recursive Powering

I am currently going through MITs course on Algorithms online for my own knowledge. One particular problem I'm having trouble with is doing asymptotic analysis on the recursive powering algorithm provided on the following page: MIT's Introduction to Algorithms, Lecture 3: Divide and Conquer - good coders code, great reuse. I've tried to write the recurrence equation for this and have:

T(n) = a when n = 1
T(n) = T(n/2) + b when n is even
T(n) = T(n-1/2) + c when n is odd

where a, b and c are all constants. I've labeled them differently just so I can keep track that while they are all constants, they are each different. For example a is the constant of returning a value, b is a constant for summing two values and c is for summing three values. I'm a bit stuck here and would like to ensure that my recurrence equation is correct and then see the steps that one would take to clearly show that T(n) = O(lg(n)). Any examples would be greatly appreciated. Thank you.

I think you mean that T(n) = T((n-1)/2) + c when n is odd.