Let $k,n,K,m \in \mathbb{N}$ such that $k<n$. Let $l\in \mathbb{R}$, such that $0 \leq l \leq 1$. I am analyzing an algorithm and I need $O(N)$. Could you help me with the reduction of the expression $N$: $$N=\log_S(1-\sqrt[K]{l})$$


$S=(\sum_{i=1}^m 2^{k-n}\binom ni)/2^{k}$

Using hint of DW, I try.

$$N=\log_S(1-\sqrt[K]{l})=\dfrac{\log_2(1-\sqrt[K]{l})}{\log_2S}=\dfrac{\log_2(1-\sqrt[K]{l})}{\log_2(\sum_{i=1}^m 2^{k-n}\binom ni)-\log_2(2^{k})}.$$

Using inequality of this answer, I get


where $H$ is the binary entropy function. In my case $m<<<n$. At this point Could you help me please?

  • $\begingroup$ What have you tried? What progress have you made? Have you tried anything? Hint: $\log_a b = \log b / \log a$. $\endgroup$ – D.W. Apr 16 '18 at 3:51
  • $\begingroup$ @D.W. I simplified the expression, but it need more simplification ... Could you help me please? $\endgroup$ – juaninf Apr 17 '18 at 9:33
  • $\begingroup$ Seems like you've found a reasonable answer. Why have you rejected it? We need a more specific question than "Could you help me?". What are you trying to achieve? What is the purpose? There are probably many equivalent formulas you could find for that expression, but we have no criteria for choosing among them. What do you want to know about this expression? Do you want to upper-bound it? Lower-bound it? Do you care only about asymptotics, ignoring constant factors? Please edit your question to make it more specific. $\endgroup$ – D.W. Apr 17 '18 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.