0
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ian Mar 17 '16 at 12:01
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Order $n!$ is much much slower after $n = 7$. You can plot two time complexities with respect to different n scales.

$\endgroup$

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.