$$2^{n-1} + 2^{n-1} + \ldots + 2$$
pretty basic question, but I'm afraid I don't know if it's $O(2^n)$ or $2^{O(n)}$
Asked
Active
Viewed 45 times
0
-
$O(2^{n})$ is a much stronger statement (smaller upperbound) than $2^{O(n)}$ because the first means $\leq C\cdot 2^{n}$ whereas the latter means $\leq 2^{Cn}$. $2^{Cn}>C2^{n}$ provided that $C$ isn't very small. – TravisJ Apr 12 '15 at 22:35
1 Answers
1
there is an exponential run time, therefore it is the first one.
This is another place to look if you are confused:
Chan Hunt
- 509