algorithmcomplexity-theorybig-orecurrencemaster-theorem

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


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!!


Solution

  • 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) + nc

    In this case you have

    Since c = logba (since 0 = log2 1), you are in case two of the Master Theorem, which solves to Θ(nc log n) = Θ(n0 log n) = Θ(log n).

    Hope this helps!