# Counterexample to big-O claim looks wrong

Let $T_1(n) = O(f(n))$ and $T_2(n) = O(f(n))$.

Then $T_1(n) / T_2(n) = O(1)$ is a false statement. A counterexample is $T_1(n) = n^2$, $T_2(n) = n$, and $f(n) = n^2$.

I don't get this counterexample, if $T_2(n) = n$, then $T_2$ is $O(n)$ and not $O(n^2)$. (As indicated by $T_2 = O(f(n))$ and $f(n) = n^2)$. Therefore, this doesn't look like a valid counterexample to me. Am I wrong?

• You have not absorbed the definition of O. – Raphael Feb 4 '17 at 10:29

The counterexample is fine. Any function that is $O(n)$ is also $O(n^2)$ – if a function's "smaller than" $n$, it's also "smaller than" $n^2$.
And note that even weaker statements are false. In fact, there is no function $g$ such that $T_1,T_2=O(f)$ implies that $T_1(n)/T_2(n)=O(g(n))$. For example, take $T_1(n)=1$ and $T_2(n)=1/g(n)^2$. So, now, $T_1(n)/T_2(n) = g(n)^2\neq O(g(n))$.
It's a trick question. There is a difference between O (f(n)) and $\Theta (f(n))$. The first one means "not greater than some constant times f (n)". The second means "not greater than some constant times f (n), but also not less than some other constant > 0 times f (n)".
People often write O (f(n)) when they mean $\Theta (f(n))$. For example, if I say I can sort an array in O (n log n), that's fine. If I say that Heapsort takes $O (n^3)$, that's not untrue, but it will mislead many people. So if I say that $T_2 (n) = n$ is $O (n^2)$ that is misleading you, but it is indeed true.