# How can we get upper bound in terms of Big Oh notation using Master theorem?

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)

• $\Theta$ is subset of $O$, so if you obtain first, then you have, also, second. Commented Sep 26, 2021 at 21:11

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)$$

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