# Two questions about complexity class

1. Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as exponential named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower?

2. What is the name of the complexity complexity class of $O(n2^{n})$?

• If you have two questions, then ask it in two separate questions. Not in one, as you do here. Although I can give you some remarks for both, I guess. 1: Why is $2^{n-1}$ "of lower order"? 2: Why does every complexity class need to have a specific name? – Discrete lizard Apr 9 '18 at 10:20
• Note that neither of these questions is about complexity classes. A complexity class is a class of languages decidable in some resource bound in some model of computation. Your question doesn't involve languages or computational resources. – David Richerby Apr 9 '18 at 11:04

Since $2^{n-1} = \Theta(2^n)$, in (CS-style) asymptotic analysis the two functions are equivalent. They have the same "order of growth" from the point of view of asymptotic analysis.

When giving big O upper bounds, we often want to suppress lower-order information. Therefore we sometimes write $\tilde{O}(n)$ instead of $O(n\log n)$ or of $O(n\log^2 n)$, and $\tilde{O}(2^n)$ instead of $O(n2^n)$. Generally speaking, $\tilde{O}$ hides (poly)logarithmic factors, that is, $\tilde{O}(f(n))$ is the same as $O(f(n) \log^{O(1)} f(n))$.

A bound of the form $\tilde{O}(2^n)$ is an exponential bound, since $\tilde{O}(2^n) = O(3^n)$ (indeed, $O((2+\epsilon)^n)$ for any $\epsilon > 0$). In fact, sometimes when saying exponential we also allow functions of the form $2^{n^2}$ in which there is a polynomial in the exponent; and sometimes we mean it in the strict sense of $O(c^n)$ for some constant $c>1$.

Finally, let me mention that complexity classes are about the complexity of problems, not the order of growth of functions. For example, the complexity class $\mathsf{P}$ consists of decision problems solvable in polynomial time. It is not the same as the class of all polynomials.

1. Yes. Since $2^{n-1}$ is just $\frac{2^n}2$, which is a constant times $2^n$, they belong to the same complexity class $O(2^n)$.

2. It belongs in its own class. For example, it can't be of class $O(2^n)$ since, by the definition, there is no constant $c$ such that $c*2^n$ will always be greater than $n*2^n$ for any $n>n_0$, since for any $n>c$, that condition will always be false.

• What does "belongs in its own class" mean? There are infinitely many functions that are $\Theta(n2^n)$, and the function $n2^n$ is in infinitely many classes of the form $O(f)$ (e.g., $O(n^22^n)$, $O(36\times2^{n^2}+2^n-4)$, ...). – David Richerby Apr 9 '18 at 11:05
• @David Richerby a function belongs to infinitely many big-O complexity classes. What I said (in an informal way) was that the smallest of these was $O(n2^n)$, which is $O(f)$ where $f$ is the actual function in this case. – Alexandre Pinho Apr 9 '18 at 18:02
• They're not complexity classes (see my comment on the question). Normally, when one says that something is "in its own category/class/set/whatever", that means that it's the only thing in that set. – David Richerby Apr 9 '18 at 18:33
• I wasn't sure how to phrase it, and so my language is inaccurate. Feel free to correct my post. – Alexandre Pinho Apr 10 '18 at 12:39