0
$\begingroup$

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.

  • 0
    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.2012-01-28

1 Answers 1

1

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

  • 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.2012-01-28