2
$\begingroup$

I would like to find some approximation or upper & lower bounds on the next simple expression: \begin{align} \sum_{i = 0}^{k} \binom{h}{i} \qquad h \geq k \end{align} But I need this approximation/bounds to be computable in polylogarithmic time - i.e. in: \begin{align} O(\log_{}^{c} h) \qquad c \in N \end{align}

If you still follow you may be intrested in my specific problem: given two numbers: \begin{align} n, k \in N \qquad n \geq 2^k \end{align} find in polylogarithmic time (as function of n) a number: \begin{align} h \in N \end{align} such that: \begin{align} \sum_{i = 0}^{k} \binom{h-1}{i} < n \le \sum_{i = 0}^{k} \binom{h}{i} \end{align} It is obvious that: \begin{align} \lceil \log_{2}n \rceil \leq h \leq n-1 \end{align} Thanks in advance.

  • 0
    I agree with Jonathan.2012-11-10

1 Answers 1

0

After thinking about this for few more hours, I came up with a solution to my specific problem (with no approximations):

Claim: The specified problem is computable in $O(\log^3n)$.

Proof: Note that $n \ge 2^k \rightarrow k \le log_2n \rightarrow k=O(\log n)$

Lemma: The comparison of $\sum_{i = 0}^{k} \binom{h}{i}$ with $n$ is computable in $O(k\log n)$

Proof of lemma: consider the following algorithm:

$1.\;choose \leftarrow 1 \\ 2.\;sum\leftarrow 0 \\3.\;for \; i=1 \; to \; k \; do: \\ 3.1. \;\;\; sum \leftarrow sum+choose \\ 3.2. \;\;\; choose \leftarrow choose * \frac{h-i}{i+1}\\ 3.3. \;\;\; if \; sum >n \; break \; (exit \; the \; loop) \\ 4. \; comapare \; n \; with \; sum$

Make sure you understand why this works. Since in any iteration $sum,choose,h,i=O(n)$ and there is a constant amount of arithmetic calculations on this numbers, each iteration takes $O(\log n)$. When we sum all the $\le k+1$ itertions we get total of: $O(k\log n) = O(\log^2n)$.

So as we know how to compare in $O(\log^2n)$, and we know that $\lceil \log_{2}n \rceil \leq h \leq n-1$ (i.e. $O(n)$ possible values), we can binary search $h$ and in each step make the two $O(\log^2n)$ comparissons $\sum_{i = 0}^{k} \binom{h-1}{i} < n \;,\; n \le \sum_{i = 0}^{k} \binom{h}{i}$, yielding a total of $O(\log^3n)$.