0
$\begingroup$

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)
Improve this question
$\endgroup$
1
  • $\begingroup$ $\Theta$ is subset of $O$, so if you obtain first, then you have, also, second. $\endgroup$
    – zkutch
    Sep 26, 2021 at 21:11

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I just realized that I typed the wrong expression. Thanks for the answer. $\endgroup$
    – five_star_021
    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
    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
    Oct 3, 2021 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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