Consider the following functions: f₁ = (n!)1/n, f₂ = log nn, f₃ = n√n and f₄ =…
Consider the following functions:
f₁ = (n!)1/n, f₂ = log nn, f₃ = n√n and f₄ = n log n log log n
Determine the order of functions by increasing order of growth.
Answer: D. f₁, f₂, f₄, f₃ — Answer: (n!)^{1/n}, log(n^n), n log n log log n, n^{√ n} Justification: (n!)^{1/n} = Θ(n). By Stirling's approximation n! ~ √(2πn) (n/e)^n, so (n!)^{1/n} ≈…
- A.
f₁, f₂, f₃, f₄
- B.
f₂, f₁, f₃, f₄
- C.
f₂, f₁, f₄, f₃
- D.
f₁, f₂, f₄, f₃
Attempted by 164 students.
Show answer & explanation
Correct answer: D
Answer: (n!)^{1/n}, log(n^n), n log n log log n, n^{√ n}
Justification:
(n!)^{1/n} = Θ(n). By Stirling's approximation n! ~ √(2πn) (n/e)^n, so (n!)^{1/n} ≈ n/e · (2πn)^{1/(2n)} = Θ(n).
log(n^n) = n log n = Θ(n log n). So this grows faster than Θ(n) because of the extra log n factor.
n log n log log n = Θ(n log n log log n). This is larger than n log n for sufficiently large n due to the additional log log n factor.
n^{√ n} grows far faster than the previous functions. Taking natural logs: ln(n^{√ n}) = √ n · ln n, while ln(n log n log log n) = ln n + ln ln n + ln ln ln n. For large n, √ n · ln n ≫ ln n + lower order terms, so n^{√ n} dominates.
Therefore the functions in increasing order of growth are: (n!)^{1/n}, log(n^n), n log n log log n, n^{√ n}.