0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by Yuval Filmus, ryan, Evil, Juho, xskxzr May 26 at 2:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Use the master theorem. $\endgroup$ – Yuval Filmus May 25 at 18:56
0
$\begingroup$

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?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.