# 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.

## marked as duplicate by Yuval Filmus, ryan, Evil, Juho, xskxzrMay 26 at 2:09

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?