Rewriting an equation in the terms of Algorithmic complexity.

Question

In this paper (page 7 Eq. 3) the author derives the following: $$\binom{n}{2b+1}\left( \frac{2}{cn\cdot 2^f}\right)^{2b}=\Omega\left( \frac{n}{4^{bf}}\right)$$ I have tried to do the same below, but first some preliminaries. This is an analysis for algorithms and therefore constants can be erased. In this example, $b$ is a constant while $f$ is some $f$-bit fingerprint. I assume that $f$ is not treated as a constant here. $n$ is the number of elements and $c$ is just some constant. My take is the following, and note that the binomial coefficients is converted into its lower bound: $$\binom{n}{2b+1}\left( \frac{2}{cn\cdot 2^f}\right)^{2b}= \frac{n^{2b+1}}{(2b+1)^{2b+1}} \frac{(2b+1)^{2b+1}}{2^f\cdot cn} = \frac{n}{1}\cdot\frac{1}{4^{f}\cdot n}=\frac{1}{4f}$$ Note that $n^{2b+1}=n^{2b}\cdot n = 2n = n$ because its algorithms and their analysis.. My result above is not the same as the one at the top of this question. How does the author derive that? How is $n$ kept in his result?

Answer 1

We have $$\left( \frac1{n} \right)^{2b}=\frac1{n^{2b}}$$

Since the first term has $n^{2b+1}$ in the numerator and the second term has $n^{2b}$ in the denominator, overall, we have $n$ in the numerator.

Also, $$\left(\frac1{2^f} \right)^{2b}=\frac1{4^{bf}}$$

Note that we don't drop constant in the exponent.

Answer 2

It's not true that constant "can be erased" in complexity analysis. You can erase multiplicative and (most of the time) additive constants, but not in exponent. For example, $\Omega(2n + 3) = \Omega(n)$, but $\Omega(n^2) \neq \Omega(n)$.

$$\binom{n}{2b+1} = \frac{n \cdot (n - 1) \cdot \ldots \cdot (n - 2b)}{(2b + 1)!} = n^{2b + 1} \cdot \prod\limits_{i=0}^{2b}\frac{n}{n - i} \cdot \frac{1}{(2b + 1)!} = n^{2b + 1} \cdot \Omega(1) = \Omega(n^{2b + 1})$$

$$\left( \frac{2}{cn\cdot 2^f}\right)^{2b} = \frac{1}{n^{2b}} \cdot 2^{2b} \cdot c^{-2b} \cdot 2^{-2bf} = \Omega(2^{-2bf}\cdot n^{-2b})$$

Multiplying right hands we get the answer.