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.

  • $\begingroup$ 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$? $\endgroup$ – GEdgar Jan 28 '12 at 14:18
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Artium Jan 28 '12 at 16:50

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.