# Time Complexity and big-O in CS

Suppose you have 2 algorithms, named A1 and A2 that are designed for solving a problem, with time complexity of $n^2\cdot 2^n$ and $n!$, respectively, where n is the size of the problem instance to solve. Which algorithm is faster?

I'm leaning towards $n!$, but I'm not sure...

• The ratio of the two is $r_n=\frac{n^2 2^n}{n!}$. Simplify $\frac{r_{n+1}}{r_n}$ to get a feel for how $r_n$ changes with $n$. – Ian Mar 17 '16 at 12:01

Note that $2^n$ consists of $n$ factors $2$, and $n!$ of $n$ factors $n,n-1,n-2,\ldots,2,1$. For $n$ large, almost all the factors of $n!$ are individually greater than $2$, and only one is less than $2$ (the factor $1$).
Intuitively, I think of the comparison between $n^22^n$ and $n!$ as a "battle of factors", where I try to group the factors of $n!$ to "take out" each factor of $n^22^n$. To take out the $n^2$, I simply reserve the first three factors $n, n-1, n-2$ from $n!$. This makes sense, as a cubic polynomial will by standard calculus eventually be greater than a quadratic (both leading coefficients positive).
If $n$ is large enough, we can easily let the factors $4,5,6,7$ from $n!$ match $2$ factors $2$ each, making up for the fact that we used up $n, n-1,n-2$ to beat $n^2$, as well as taking care of the factor $2$ of $n^22^n$ that the $1$ from $n!$ would have had trouble with.
All remaining factors of $n!$ (except for the $1$) can now take out at least one factor $2$ of $n^22^n$ each, so the $n!$-side "wins the battle". That means that $n!>n^22^n$ for large enough $n$. Then $n!$ takes more time, so that the $n^22^n$ algorithm is more efficient.
Order $n!$ is much much slower after $n = 7$. You can plot two time complexities with respect to different n scales.