1
$\begingroup$

I am currently working on CLRS 1.13. The idea is to use Stirling's approximation to prove that

$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$

Now directly replacing Stirling's approximation I arrive to something like:

$${2n \choose n} = \frac{2^{2n} \left( 1 + \Theta(\frac{1}{2n}) \right)}{ \sqrt{\pi n} \left(1 + \Theta( \frac{1}{n}) \right)^2 }$$

Now the quotient is a function that ends up being $O(\frac{1}{n})$ because we have terms in $O(\frac{1}{n})$ and $O(\frac{1}{2n})$. The problem is that even if there is a quotient of two functions that are $O(\frac{1}{n})$.

I don't know if the result is still $O(\frac{1}{n})$. In fact I haven't seen any general rule for the quotient of two big $O$ s.

Is there a general rule that I can apply here?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Just simply use the inequality $1 + \Theta(1/n) \geq 1$ in the denominator. You will get the required answer.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @plop $f(n)$ is positive right? so the inequality should be correct for all $f \in \Theta(1/n)$. $\endgroup$
    – Inuyasha Yagami
    Commented Feb 1, 2021 at 16:59
  • $\begingroup$ I was wrong. I was reading $\Theta$ and thinking $O$. For $n$ large, the elements of $\Theta$ do become positive. $\endgroup$
    – plop
    Commented Feb 1, 2021 at 17:02
  • $\begingroup$ @plop I am not aware of the definition of $\Omega$ or $O$ for negative functions. :p $\endgroup$
    – Inuyasha Yagami
    Commented Feb 1, 2021 at 18:09
  • $\begingroup$ @plop However, in Stirling's approximation, the function $f$ is indeed positive. $\endgroup$
    – Inuyasha Yagami
    Commented Feb 1, 2021 at 18:10
  • 1
    $\begingroup$ It is the same definitions. They don't make any assumption about the sign of the function. In the case of $\Theta(1/n)$ it follows as a consequence of the definition, since $f\in\Theta(1/n)$ must satisfy $K_1/n\leq f(n)\leq K_2/n$ for some $K_1,K_2>0$ and sufficiently large $n$. $\endgroup$
    – plop
    Commented Feb 1, 2021 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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