Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)
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) $$
