# Trouble finding what this recurrence solves to [duplicate]

I have a recurrence relation of the form $$T(n) = 2T(n/2)+O(1)$$

I'm not sure how to deal with the big $$O$$-notation in the problem in order to start solving it ? Any help would be appreciated.

• Use the master theorem. – Yuval Filmus May 25 '19 at 18:56

Hint: can you solve it for $$n = 2^k$$ where we replace $$O(1)$$ with constant $$c$$ and let $$f(1) = c$$? Then you have:
$$f(2^k) = 2f(2^{k-1}) + c$$
Then the pattern starts $$f(1) = c$$, $$f(2) = 3c$$, $$f(4) = 7c$$, $$f(8) = 15c$$... any guesses?