1
$\begingroup$

I am simplifying a big formula to find the big notation of a certain algorithm. The expression is:

$$\log_2(1-l)/\log_2(1-2^{nH(m/n)-n})$$

where $0.98<l< 1$, $0<m<n/2$, $n>0$ and $H$ is the binary entropy function.

In practice, I known that the algorithm is exponential, but I do not known how simplify that to get the exponential expression. Could you help me please?

$\endgroup$
5
  • $\begingroup$ Do you mean simplifying to big-oh notation or exact simplification? $\endgroup$
    – orlp
    Apr 22, 2018 at 12:53
  • $\begingroup$ to big notation $\endgroup$
    – juaninf
    Apr 22, 2018 at 13:26
  • $\begingroup$ As a function of $n$? As a function of both $m$ and $n$? What's wrong with the expression you already have? That looks like it's already an answer to your question. $\endgroup$
    – D.W.
    Apr 22, 2018 at 16:29
  • $\begingroup$ @D.W. as function of $n$ and $m$. $\endgroup$
    – juaninf
    Apr 22, 2018 at 16:52
  • $\begingroup$ Try using the estimate $\log (1-x) = -x-O(x^2)$, valid for $x$ bounded away from 1. $\endgroup$ Apr 22, 2018 at 19:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.