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

$\endgroup$
4
  • $\begingroup$ I just realized that I typed the wrong expression. Thanks for the answer. $\endgroup$ Sep 27 at 0:34
  • $\begingroup$ I will accept your answer once you make corrections. Sorry for that. $\endgroup$ Sep 27 at 0:49
  • $\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 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 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.