# What is the difference between $O$ and $\widetilde{O}$?

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$$?

• 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".
– Stef
Feb 9 at 7:51
• Then what implies $a < b$? How what? I don't understand your question.
– Stef
Feb 9 at 8:01
• 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$.
– Stef
Feb 9 at 8:15
• 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$. Feb 9 at 11:18
• @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.
– Stef
Feb 9 at 12:19