We know that $\widetilde{O}(f(n))$$O$ with a tilde above it — which means $O(f(n) \text {polylog}(f(n)))$, i.e., $O(f(n) (\log f(n))^k)$ for some $k$.

Also I have seen in Wikipedia that $n2^n=\widetilde{O}(2^n).$

My question is that if $\text{poly}(n) \space 2^{xn}\leq2^{yn}$ then how it implies $x\leq y$? I have seen many places this types of inequality holds. How the calculation is happening here by which we get $x\leq y$?

  • 1
    $\begingroup$ If $k, a, b$ are constants such that $0 < a < b$, then $n^k 2^{an} << 2^{bn}$. I don't know what you mean by "get x = y". $\endgroup$
    – Stef
    Feb 9 at 7:51
  • 1
    $\begingroup$ Then what implies $a < b$? How what? I don't understand your question. $\endgroup$
    – Stef
    Feb 9 at 8:01
  • 1
    $\begingroup$ Alright. So first note that $\operatorname{poly}(n) 2^{an} \leq 2^{bn}$ is equivalent to $\operatorname{poly}(n) \leq 2^{(b-a)n}$. But if $b-a < 0$, then $2^{(b-a)n} < 1$ for all positive $n$. Since $\operatorname{poly}(n) > 1$ for $n$ big enough, we must have $b - a > 0$. $\endgroup$
    – Stef
    Feb 9 at 8:15
  • 1
    $\begingroup$ Basically, you need to see what the limit $\lim_{n\rightarrow\infty} \frac{2^{n(x+\epsilon)}}{n^k2^{nx}}$ evaluates to for any $k,\epsilon\ge0$. $\endgroup$
    – rus9384
    Feb 9 at 11:18
  • 1
    $\begingroup$ @rus9384 Showing direction $b > a \implies \exists N, \forall n > N, n^k 2^{an} < 2^{bn}$, yes, is showing that polynomials are dominated by exponentials in the neighbourhood of infinity; but the reverse direction is much easier; to show direction $n^k 2^{an} < 2^{bn} \implies b > a$, suffices to say that function $x \mapsto 2^x$ is increasing. $\endgroup$
    – Stef
    Feb 9 at 12:19


Your Answer

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