Solving the recurrence T(n) = T(n / 2) + O(1) using the Master Theorem?

Question

I'm trying to solve a recurrence relation to find out the complexity of an algorithm using the Master Theorem and its recurrences concepts, how can I prove that:

T(n) = T(n/2)+O(1)

is

T(n) = O(log(n)) ?

Any explanation would be apprecciated!!

Answer 1

Your recurrence is

T(n) = T(n / 2) + O(1)

Since the Master Theorem works with recurrences of the form

T(n) = aT(n / b) + n^c

In this case you have

• a = 1
• b = 2
• c = 0

Since c = log_ba (since 0 = log₂ 1), you are in case two of the Master Theorem, which solves to Θ(n^c log n) = Θ(n⁰ log n) = Θ(log n).

Hope this helps!