Solving the recurrence T(n) = T(n / 2) + O(1) using the Master Theorem?
24,882
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
- a = 1
- b = 2
- c = 0
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!
Author by
Admin
Updated on January 28, 2020Comments
-
Admin over 4 years
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!!
-
Admin about 4 yearsThank you for the explanation!!