recurrence using Master theorem

Question

can we solve this T(n) = T(n/2) + 1  using master theorem?

Comments

it is easy if recursive step is taking more time than the additional operations then that is the time complexity of the recurrence relation and also

if the additional operations( excluding recurrence) are taking more time then that is the time complexity for whole.

---

https://www.youtube.com/watch?v=iT_Scp0hWWU&index=8&list=PLAvNF-IjWaN4Dc4zA02fA7muqvQ46KCDF
Watch this and you can teach your kids how to use master's theorem :P

---

@Mk Utkarsh Thanks for the explanation and the video :)

Answer 1

Yes. This can be easily done by Master's Theorem.

For applying Master's Theorem to relation of the form,

[T(n) = aT(n/b) + $n^{k}$], where 'k' is degree of 'n' or highest power of 'n'

we need to compare $log_{b}a$ and compare it with 'k;

Here, a = 1, b = 2 and k = 0

So $log_{b}a$ = k and for this condition,

T(n) = O(f(n) * logn) = O(1*log n) = O(log n)