why do we use big-$O$ in solving recurrence relations Solving recurrence by substitution, first guess $f(n)$ then prove $T(n)=O(f(n))$.
For example, $T(n)=2T(n/2)+n$. My guess $f(n)=n\lg n$, and then I prove it by induction that $T(n)=O(n\lg n)$.
What is confusing is why do we use big-$O$ to solve the recurrence? I mean, I can prove that $T(n)=O(N^2)$, but that doesn't solve the recurrence, we should've used big-theta instead since it's a tight bound. What am I missing?
 A: Let $f = O(x)$. It is obvious that $f = O(x^{c})$ and $f=O(c^{x})$ for $c>1$ and in general case $f=O(y)$ for $\forall y>x$, but in the theory of computing we consider always the lowest possible bound.
In your example, $f=O(n\log{n})$. $f=O(x)$ for $x>n\log{n}$, too. But we consider the lowest bound that is $n\log{n}$.   
For $\Theta$, we say $f=\Theta(x)$, we must show two things: $f=O(x)$ and $f=\Omega(x)$.
A: I think that this in some sense depends on the context in which you're working. So if, for example, you were in an introductory computational complexity course, one motiviation for using $O$ notation instead of $\Theta$ notation is that your professor may want you to be able to step through the process more slowly and recognize that the ability to use $\Theta$ necessarily depends on $O$ and $\Omega$, on both the upper and the lower bounds. 
Another possible reason is that you wish to find the lowest possible upper bound, not just any upper bound; as Hasan Heydari pointed out, it matters most how slow the algorithm can possibly. This is because the big question in computational complexity is to see whether or not a whole big class of problems called $NP$ have algorithms with polynomial upper bounds. In this regard, we don't necessarily care $\Omega$ what the lower bound for the running time is, and thus don't necessarily care about the more exact running time $\Theta$.
