# Asymtotic Complexity Analysis using logarithms and binomial coefficients

On page 11 of "Smaller decoding exponents: ball-collision decoding" by Berstein et.al. they have the formula $$\lim_{n \rightarrow \infty} \frac{1}{n}\log_{2}\left(\dbinom{k_{1}}{p_{1}}\dbinom{l_{1}}{q_{1}} + \dbinom{k_{2}}{p_{2}}\dbinom{l_{2}}{q_{2}} +\dbinom{k_{1}}{p_{1}}\dbinom{k_{2}}{p_{2}}\dbinom{l_{1}}{q_{1}}\dbinom{l_{2}}{q_{2}}2^{-l_{1}-l_{2}} \right)$$ $$= max\Bigg[(R/2)log_2(R/2) - Plog_2P-(R/2-P)log_2(R/2-P) + Llog_2L -Qlog_2Q$$ $$-(L-Q)log_2(L-Q),(R)log_2(R/2) - 2Plog_2P-(R-2P)log_2(R/2-P) + 2Llog_2L$$ $$-2Qlog_2Q -2(L-Q)log_2(L-Q)-2L\Bigg]$$ where $p_i/n \rightarrow P, q_i/n \rightarrow Q, k_i/n \rightarrow R/2,$ and $l_i/n \rightarrow L$ as $n \rightarrow \infty$

They apparently used $$\frac{1}{n}\log_{2}\dbinom{(\alpha + o(1))n}{(\beta +o(1))n} \rightarrow \alpha \log_{2}\alpha - \beta\log_{2}\beta - (\alpha - \beta)\log_{2}(\alpha - \beta)$$ as n $\rightarrow \infty$ but I don't see how they ended up with a max function with two arguments. I'm not even sure how to deal with the sum inside the logarithm. Any ideas? Thanks!

-
Let $L = \log(\max(x,y))$. Then $\log(x+y)$ is between $L$ and $\log(2\max(x,y)) = L + \log 2$. Division by $n$ makes the constant $\log 2$ negligible, so we're left with the asymptotics of $L / n$. – Noam D. Elkies Mar 13 '12 at 5:05
Thanks Noam! I apologize if this question isn't research level. I'll stick to MSE from now on. – Nick Peterson Mar 14 '12 at 2:52