Expressing pseudo-polynomial runtime solely in terms of the input size
You are correct that the running time is $O(n^2 2^n)$, but according to the definition of big O, it is not the case that $n^2 2^n = O(2^n)$, since $n^2 2^n$ grows faster than $2^n$. What is true is that for every $\epsilon &gt; 0$, $n^2 2^n = O((2+\epsilon)^n)$.

Often it is convenient to hide such "small" factors, and write $O(n^2 2^n) = \tilde{O}(2^n)$. The usual definition of $\tilde{O}(\cdot)$ is this: $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log g(n))^k)$. In practice this is almost always used when $g(n)$ is either a polynomial or an exponential. When $g(n)$ is a polynomial, $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log n)^k)$, and we say that $\tilde{O}$ hides polylogarithmic factors. When $g(n)$ is exponential (that is, $g(n) = e^{An^B}$ for some $A,B&gt;0$), $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n) n^k)$, and we say that $\tilde{O}$ hides polynomial factors.