<p>If you have an exact and simple formula like $O(n2^n)$ I would go with that. It is more precise than $O((2+\epsilon)^n)$ because it tells you what the epsilon really is. For the same reason I would generally prefer $O(2^{n/2})$ (but with a slashed fraction not a vertical one in the exponent) to $O(1.42^n)$, although in some cases you might want to give the numerical value (or both forms) to show more clearly how a bound compares to previous bounds for the same problem.</p>

<p>If the formula is more complicated ($c^n$ where $c$ is the largest real root of a higher-degree polynomial, say) it can be helpful to replace $c$ by a numeric value. In this case $c$ should always be rounded up, not down, and lower-order terms like the factor of $n$ in the first formula should be omitted (because they are covered by the rounding of $c$).</p>

CC BY-SA 3.0
2015-04-13T08:34:27.737Z
For $2^n$ times a messy polynomial, there is also the option to write $\tilde O(2^n)$.
Emil Jeřábek
CC BY-SA 3.0
2015-04-12T19:34:34.040Z
2015-04-12T19:34:34.040Z
David Eppstein
<p>Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar transformations, I was wondering what people prefer.</p>

<notation><asymptotics>
Preferable way to express $O(n2^n)$
Elliot Gorokhovsky
# Preferable way to express $O(n2^n)$

(Asked by: username_0 on 2015-04-12)

Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar transformations, I was wondering what people prefer.

**Tags:** notation, asymptotics


---

## 1 answers

### Answer by username_1 on 2015-04-12. Score: 15 | Accepted answer

If you have an exact and simple formula like $O(n2^n)$ I would go with that. It is more precise than $O((2+\epsilon)^n)$ because it tells you what the epsilon really is. For the same reason I would generally prefer $O(2^{n/2})$ (but with a slashed fraction not a vertical one in the exponent) to $O(1.42^n)$, although in some cases you might want to give the numerical value (or both forms) to show more clearly how a bound compares to previous bounds for the same problem.

If the formula is more complicated ($c^n$ where $c$ is the largest real root of a higher-degree polynomial, say) it can be helpful to replace $c$ by a numeric value. In this case $c$ should always be rounded up, not down, and lower-order terms like the factor of $n$ in the first formula should be omitted (because they are covered by the rounding of $c$).

> **Comments:**
> **username_2**: For $2^n$ times a messy polynomial, there is also the option to write $\tilde O(2^n)$.  

---

