Is $n4^n$ greater or within the realm of $\theta{\left(4^n\right)}$

Question

Basically a Big O question. Is $n4^n$ or any other exponential function greater than $4^n$ in terms of Big O notation or not?

Answer 1

We say that $f(n) \in \Theta (g(n)) \iff \exists c_1, c_2\ {\rm and}\ n_0\ s.t. 0 \le c_1 g(n) \le f(n) \le c_2 g(n)\ \forall\ n \ge n_0$. That is, for sufficiently large $n$, we can bound $f(n)$ above and below by multiples of $g(n)$. So for instance, the function $f(n) = a n^3 + b n^2 + c n + d$ is in $\Theta (n^3)$ because for sufficiently large $n_0$, the $n^2$, $n$ and constant terms will be small compared to $n^3$, so the $n^3$ is the only one "that matters." (Clearly $f(n)\ \in \Theta (n^4)$ as well.) Now consider the problem here, involving $f(n) = n 4^n$. Suppose you think you have found an $n_0$ such that above $n_0$ $c_1 4^n \le n 4^n \le c_2 4^n$. Well, then I will just increase the value of $n$ to be greater than your (fixed) $c_2$, so that your bounds do not hold. I can always do that. In short, $n 4^n$ is not in $\Theta (4^n)$.