Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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