# 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

## 2 Answers

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.