Question

Consider the following functions, where \(n\) is a positive integer.

\[ n^{1/3}, \quad \log(n), \quad \log(n!), \quad 2^{\log(n)} \]

Which one of the following options lists the functions in increasing order of asymptotic growth rate?

Note: Assume the base of log to be 2.

• A. \( \log(n), \; n^{1/3}, \; 2^{\log(n)}, \; \log(n!) \)
• B. \( n^{1/3}, \; \log(n), \; \log(n!), \; 2^{\log(n)} \)
• C. \( \log(n), \; n^{1/3}, \; \log(n!), \; 2^{\log(n)} \)
• D. \( 2^{\log(n)}, \; n^{1/3}, \; \log(n), \; \log(n!) \)

Hint:

Simplify $2^{\log n}$ to $n$ first, recall $\log(n!)$ grows like $n\log n$, and remember any positive power of $n$ eventually beats any power of $\log n$.

Answer 1

The Correct Option is A

The fastest way through this question is to rewrite every function in a form that is directly comparable, then rank them using standard growth-rate facts rather than plugging in numbers.

1. $2^{\log(n)}$: since the log is base 2, this simplifies exactly to $n$, because raising 2 to the power of "the exponent that gives n" just gives back n. So this term behaves like a plain linear function.
2. $\log(n!)$: using $\log(n!) = \log 1 + \log 2 + \cdots + \log n$, and comparing this sum to $n \log n$, since each of the n terms is at most $\log n$, and roughly half of them, from $n/2$ to $n$, are at least $\log n - 1$, $\log(n!)$ is of the order $n \log n$. This is strictly bigger than plain $n$ for large $n$, since it has an extra growing factor of $\log n$ multiplied in.
3. $n^{1/3}$ versus $\log(n)$: any positive power of $n$, however small the exponent, eventually outgrows any power of $\log n$. Substituting $n = 2^m$ turns $n^{1/3}$ into $2^{m/3}$, exponential in $m$, and $\log(n)$ into $m$, linear in $m$, and exponential growth always eventually beats linear growth. So $n^{1/3}$ overtakes $\log(n)$ once $n$ is large enough.

Putting the four on one scale: $\log(n)$ is the slowest, logarithmic growth, then $n^{1/3}$, since a fractional power beats any power of log, then $2^{\log(n)} = n$, since a full linear power beats a 1/3 power, and finally $\log(n!) \sim n\log(n)$ is the fastest since it is linear times an extra logarithmic factor.

Let's summarize:

• $2^{\log(n)}$ collapses to plain $n$.
• $\log(n!)$ grows like $n\log(n)$, faster than plain $n$.
• Any positive power of $n$ beats any power of $\log(n)$, so $n^{1/3}$ beats $\log(n)$, and $n$ beats $n^{1/3}$.

So the increasing order is $\log(n) < n^{1/3} < 2^{\log(n)} < \log(n!)$, which is option (A).

\[ \boxed{\log(n) < n^{1/3} < 2^{\log(n)} < \log(n!)} \]