0
$\begingroup$

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?

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

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))$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.