Solving the recurrence T(n) = T(n / 2) - T(n / 6) + O(lg n) using the master theorem method?

The substitution method suggests we guess the solution, and then prove it by induction.

Here we guess the partial solution: T(2^k) = k+1

• The base case: T(2^0) = T(1) = 1.
• The induction case for k>0: T(2^k) = T(2^(k-1)) + 1 = k-1+1 + 1 = k+1

This gives us that T(n) = lg(n) + 1 for n a power of 2. To extend this to a full solution, let n' be the smallest power of 2 greater than or equal to n (for arbitrary n>0). Then T(n) <= T(n') = lg(n') + 1. Since n' < 2n, we have lg(n') < lg(2n) = lg(n) + 1. So T(n) < lg(n) + 2.

Thus we've proved T(n) = O(lg(n)).

It is O(log₂(n)):

                    __
T(n)   = T(n/2) + 1   |
T(n/2) = T(n/4) + 1   | 
T(n/4) = T(n/8) + 1   |-- k operations
...                   |
T(1)   =          1 __|

n/2^k = 1  =>  n = 2^k  =>  k = log₂(n)   (by definition of log₂).

Many standard recurrence relations can be easily solved using the Master's theorem. It has three cases.

Your recurrence relation breaks to case #2 with a equals 1, b equals 2, and f(n) equals 1.