# Big O Notation Arithmetics

Assuming it is known that:

$$t\sqrt n = O((nt)^{2/3}+n+t)$$

How is it possible to deduce a bound on $t$?

Specifically, I need to prove that $t = O(\sqrt n)$. This is part of a bigger question, so I am not sure the above formula is correct. I would like to know in general how to solve such problems.

-
You need some "as" clause when you use O notation. For example, "as $n \to +\infty$". Is that what you want? For each fixed $t$? Uniformly in $t$? What? $t$ is a function of $n$? – GEdgar Jan 28 '12 at 14:18
Thank you, my question was already answered, but I am not sure I fully understand what you wrote. t is not a function of n, but I needed to prove that it is bounded by a function of n. To be more specific, n is number of points on the plane, t is number of lines with exactly $/sqrt n$ points on each. – Artium Jan 28 '12 at 17:10

Assume that $t\sqrt{n}\leqslant c\cdot((nt)^{2/3}+n+t)$ for every $n\geqslant n_0$.
Choose $n_0$ large enough for $n_0\geqslant4c^2$ to hold. Then, $ct\leqslant\frac12t\sqrt{n}$ for every $n\geqslant n_0$, hence $t\sqrt{n}\leqslant2c\cdot((nt)^{2/3}+n)$, that is $x\leqslant2c\cdot(x^{2/3}+1)$, where $x=t/\sqrt{n}$.
Since $z-2c\cdot(z^{2/3}+1)\to+\infty$ when $z\to+\infty$, $z-2c\cdot(z^{2/3}+1)\gt0$ for every $z$ large enough, say $z\gt K_c$. This means that $x\leqslant K_c$, that is, that $t\leqslant K_c\sqrt{n}$ for every $n\geqslant n_0$.
Thank you. Can you explain how did you choose $n_0$ ?. Was your intuition to eliminate the $t$ at the end? If you did something before writing the proof itself, I would like to see it so I can understand how to solve these problems myself. – Artium Jan 28 '12 at 16:50