How to find asymptotic of $\sum_{k=0}^{\lfloor\log(n) \rfloor} \lceil \frac{n}{2^k} \rceil$

Question

My rough estimates are the following: $\lceil \frac{n}{2^k} \rceil \le \frac{n}{2^k} + 1$, so sum $\le \lfloor\log(n) \rfloor + n*\sum_{k=0}^{\lfloor\log(n) \rfloor} \frac{1}{2^k} \le 2n(1-1/n) + \lfloor\log(n) \rfloor = O(n)$. Am I right? And are there more accurate estimates?

Answer 1

Let $S(n):=\sum\limits_{k=0}^{\lfloor\log_2n\rfloor}\left\lceil\frac{n}{2^k}\right\rceil$. Using $x\leq\lceil x\rceil\leq x+1$, so:

$$S(n)\leq\sum\limits_{k=0}^{\lfloor\log_2n\rfloor}\frac{n}{2^k}+1=n\sum\limits_{k=0}^{\lfloor\log_2n\rfloor}\frac{1}{2^k}+\sum\limits_{k=0}^{\lfloor\log_2n\rfloor}1\leq n\sum_{k=0}^\infty\frac{1}{2^k}+\log_2n=2n+\log_2n,$$ So $S(n)\in O(n)$.

Similarly, note that, using $x-1\leq\lfloor x\rfloor\leq x$:

$$S(n)\geq\sum\limits_{k=0}^{\lfloor\log_2n\rfloor}\frac{n}{2^k}=n\sum\limits_{k=0}^{\lfloor\log_2n\rfloor}\frac{1}{2^k}=n\frac{1-(1/2)^{\lfloor\log_2n\rfloor+1}}{1-1/2}\geq 2n\left(1-(1/2)^{\log_2n+1}\right)=2n-n\cdot\frac{1}{n}=2n-1$$

so $S(n)\in\Omega(n)$.

Finally, $s(n)\in\Theta(n)$.