# algorithms: doubts about some inequalities used in asymptotic analysis

I was reviewing this recent article and had a couple of doubts in the final analysis of the complexity of the scheme (it is not necessary to review the entire document). I included three questions here, since I thought they seemed simple questions.

1. On page 17 (last four lines, see after equation 7), it seems that this inequality is used (here, $$k (n) = sqrt { frac {n delta (n)} { log n}}$$ Y $$delta (n) = o (n / log n)$$):

$$frac { binom {n} {a}} { binom {^ n / _k} {^ a / _k} ^ k} leq (^ n / _k) ^ k$$

May I know proof of that?

1. Similarly, at the beginning of page 18, how is this possible? (However, the previous inequality is used to get here, $$(n / k) k / 2$$ thing, and don't worry about the meaning of $$mathtt {ss}$$)

$$mathtt {ss} leq sqrt { binom {n} { frac {n} {2} – delta (n)}} cdot (n / k) ^ {k / 2} cdot binom {k} {2 delta (n)} cdot 2 ^ {(2 delta (n) +1) n / k} leq 2 ^ {n / 2 + or (n)}$$

1. In addition, this could be a bit trivial, on page 17, an inequality above equation 7, the $$O (n)$$ The term is discarded, isn't it relevant?