Must you prove the equality condition for Big-O notation? From my understanding, $$T(n) = O(g(n)) \quad\text{iff}\quad T(n) \leq cg(n),$$ where $c > 0$ and $n >N. $
My confusion is simple. To show this is true, why must we not prove the equality? If we don't prove the equality at all and simply show that $T(n) < cg(n)$ for a set of $n$ and $c$, then wouldn't that imply that proving $T(n)$ satisfies small-o notation's condition would make it also true for Big-O notation?
 A: Two things are going on.
First of all, proving that $T(n) = o(g(n))$ does imply that $T(n) = O(g(n))$. Even though we write it with $=$ due to a confusing historical choice of notation, big-O notation is always an upper bound.
Saying $T(n) = o(g(n))$ says "$T(n)$ grows slower than $c g(n)$ as $n \to \infty$".
Saying $T(n) = O(g(n))$ says "$T(n)$ grows slower than or the same as $c g(n)$ as $n \to \infty$." The second statement includes the first.
Often, we try to state the best bound we can using big-$O$ notation. But if you are claiming that we've captured the exact rate of growth of $T(n)$ up to a constant factor, you should really be writing $T(n) = \Theta(g(n))$.

Separately, proving that there are $c>0, N$ such that $T(n) \le c g(n)$ if $N>n$ is the same as proving that there are $c>0, N$ such that $T(n) < c g(n)$ if $N>n$. There is no difference between $<$ and $\le$ here.
That's because if you have $T(n) \le c g(n)$ for one constant $c$, then $T(n) < c g(n)$ for a slightly bigger constant $c$. For example, if someone told you that $T(n) = O(n^2)$ because $T(n) \le 3n^2$ for $n>1000$, you would also know that $T(n) < 3.1n^2$ for $n>1000$, because $3n^2 < 3.1n^2$.
A: Big O is just an upper bound. For example, it is true that $n^2=O(2^n)$, even though the two functions are very far apart.
If you want to say that you have an optimal upper bound, that would be big Theta, not just big O. We say $f(n)=\Theta(g(n))$ if there exist $0<c_1<c_2$ such that $c_1g(n)\leq f(n)\leq c_2g(n)$ for $n$ sufficiently large.
