0
$\begingroup$
  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})$?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Discrete lizard Apr 9 '18 at 10:20
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Apr 9 '18 at 11:04
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$
  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.

$\endgroup$
  • 2
    $\begingroup$ 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)$, ...). $\endgroup$ – David Richerby Apr 9 '18 at 11:05
  • $\begingroup$ @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. $\endgroup$ – Alexandre Pinho Apr 9 '18 at 18:02
  • $\begingroup$ 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. $\endgroup$ – David Richerby Apr 9 '18 at 18:33
  • $\begingroup$ I wasn't sure how to phrase it, and so my language is inaccurate. Feel free to correct my post. $\endgroup$ – Alexandre Pinho Apr 10 '18 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.