6
$\begingroup$

Say I have a binomial coefficient $y=\binom{5n+3}{n+2}$ or $y=\binom{n^2+4}{3n}$ something of the sorts in terms of the variable $n$. How can I determine $f$ so that $y = O(f)$?

Is there a general method for this sort of thing. I have only ever seen $O$-notation in a computer science setting and its treatment was not concerned with deriving anything except the bounds for "simple" functions like logarithms and polynomials. As a side question, what would be a good resource to learn further methods to find $O$ of more complex functions? I understand the formal definition, but Im unsure how to use it practically.

My apologies if this is a stupid question. Its not homework.

$\endgroup$
  • $\begingroup$ It's imprecise to say "determine O(y)." What you want is to write down some nice function f such that y = O(f). (Of course what you really want is probably to write down some nice function f such that y = Theta(f).) $\endgroup$ – Qiaochu Yuan Nov 7 '10 at 20:35
  • $\begingroup$ You might also want to take a look at this question: math.stackexchange.com/questions/6784 $\endgroup$ – Mike Spivey Nov 7 '10 at 20:47
  • $\begingroup$ @qiaochu yes, thats what I meant, edited. $\endgroup$ – AnonymousCoward Nov 7 '10 at 23:11
6
$\begingroup$

Use Stirling's approximation in $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

$\endgroup$
2
$\begingroup$

The answer to your second question is to read Graham, Knuth, and Patashnik's Concrete Mathematics, at least for simpler practical examples. For complicated sequences it can be extremely difficult and in many cases open to find asymptotics, e.g. for Ramsey-theoretic sequences, so you'll have to narrow the scope of your question a little to get a reasonable answer.

$\endgroup$
  • 2
    $\begingroup$ Specifically, look at Chapter 9 of Concrete Mathematics. $\endgroup$ – Mike Spivey Nov 7 '10 at 20:42

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.