Trouble finding what this recurrence solves to
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?