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.

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.

share|improve this question
    
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).) –  Qiaochu Yuan Nov 7 '10 at 20:35
    
You might also want to take a look at this question: math.stackexchange.com/questions/6784 –  Mike Spivey Nov 7 '10 at 20:47
    
@qiaochu yes, thats what I meant, edited. –  AnonymousCoward Nov 7 '10 at 23:11
add comment

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
2  
Specifically, look at Chapter 9 of Concrete Mathematics. –  Mike Spivey Nov 7 '10 at 20:42
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.