The recursion is:

T(n) = 5T(n/2) + O(n)

I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound in terms of Big Oh. Is there any principle to convert it into Big Oh form? I read some examples where they substituted some values and deduced but I couldn't understand.

Update: I apologize for writing the recursion equation wrong. The actual recursive equation for this question is:

T(n) = 2(n-1) + O(n)
  • $\begingroup$ $\Theta$ is subset of $O$, so if you obtain first, then you have, also, second. $\endgroup$
    – zkutch
    Commented Sep 26, 2021 at 21:11

1 Answer 1


Your reasoning is wrong. It is in $\Theta(n^{\log_2(5)})$. Hence, it is also in $O(n^{\log_2(5)})$.

Answer to the update: Also, for the update part, it is wrong. You can find it by a straightforward expansion (no need to master theorem):

$$ T(n) = 2T(n-1) + O(n) = 2(2T(n-2) + O(n-1)) + O(n) \\ = 2^2T(n-2) + O(n-1) + O(n) = \cdots = \\ 2^n * T(0) + O(1) + O(2) + \cdots + O(n) \in O(2^n) $$

  • $\begingroup$ I just realized that I typed the wrong expression. Thanks for the answer. $\endgroup$ Commented Sep 27, 2021 at 0:34
  • $\begingroup$ @five_star_021 You shouldn't totally change the question to another question. You should post a new question for that matter. $\endgroup$
    – OmG
    Commented Sep 27, 2021 at 11:12
  • $\begingroup$ @five_star_021 it's better now. You can find the answer for the updated part as well. $\endgroup$
    – OmG
    Commented Oct 3, 2021 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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