Why doesn’t $T(n) = 2T(\frac{n}{2}) + O(n^2)$ solve to $T(n) = \Theta(n^2)$? I am told that the following statement is not true:
$T(n)=2 T (\frac{n}{2})+ O(n^2)$ then $T(n)=\Theta (n^2)$
My challenge is we can solve it by Master Theorem and reach to $T(n)=\Theta (n^2)$. What is wrong here that in my notes says the mentioned fact is not correct. I guess because of $O$ notation in second term but couldn't sense it !
 A: Let’s begin with a simpler problem. Suppose I say “I am at most 1km tall.” What does this statement tell you about how tall I am? The answer is “not much.” I could be 1m tall, or 2m tall, or perhaps I’m a titan and I really am 1km tall! The point is that I’ve just given a very weak bound on my height, so you don’t know what my height actually is.
Now, let’s turn to your problem. You’re given the recurrence
$$T(n) = 2T(n / 2) + O(n^2)\text.$$
Here, the $O(n^2)$ term means “some function that is asymptotically bounded from above by $n^2$.” Just as the statement “I am at most 1km tall” doesn’t actually tell you how tall I am, the $O(n^2)$ term doesn’t actually tell you what the last term in the recurrence is. Indeed, all of the following recurrences match the form of the recurrence you showed above:

*

*The recurrence $S(n) = 2S(n / 2) + 1$, which solves to $S(n) = \Theta(n)$.

*The recurrence $R(n) = 2R(n / 2) + n$, which solves to $R(n) = \Theta(n \log n)$.

*The recurrence $U(n) = 2U(n / 2) + n \log n$, which solves to $U(n) = \Theta(n \log^2 n)$.

*The recurrence $Q(n) = 2Q(n / 2) + n^2$, which solves to $Q(n) = \Theta(n^2)$.

Notice that all these recurrences have a last term that’s $O(n^2)$, though not necessarily $\Theta(n^2)$. They all solve to asymptotically different values, and only one of the sequences I listed actually solves to $\Theta(n^2)$.
In that sense, you can think of your original recurrence $T(n) = 2T(n/2) + O(n^2)$ not as a single recurrence, but as a family of different recurrence relations that all have the same general shape. While you can say that all of them solve to something that is $O(n^2)$ - that is, all recurrences in the family are asymptotically at most quadratic - you can’t say that they all solve to $\Theta(n^2)$ because as shown above that isn’t true.
Hope this helps!
