Arrange the following functions in increasing order of time complexity. f1(n)…
Arrange the following functions in increasing order of time complexity.
f1(n) = n2
f2(n) = n3log (log(n))
f3(n) = n2log (n)
f4(n) = n!
Answer: A. f1, f3, f2, f4 — Correct order: f1(n) = n^2, f3(n) = n^2 log n, f2(n) = n^3 log(log n), f4(n) = n! Compare n^2 and n^2 log n: log n → ∞ as n grows, so n^2 < n^2 log n. Compare…
- A.
f1, f3, f2, f4
- B.
f2, f4, f1, f3
- C.
f1, f2, f3, f4
- D.
None of the above
Attempted by 343 students.
Show answer & explanation
Correct answer: A
Correct order: f1(n) = n^2, f3(n) = n^2 log n, f2(n) = n^3 log(log n), f4(n) = n!
Compare n^2 and n^2 log n: log n → ∞ as n grows, so n^2 < n^2 log n.
Compare n^2 log n and n^3 log(log n): the ratio is (n^3 log(log n)) / (n^2 log n) = n * (log log n)/(log n). As n → ∞, n/(log n) → ∞, so the ratio → ∞ and n^3 log(log n) grows faster.
Factorial vs polynomials: n! grows faster than any polynomial (and polynomial times slowly varying logs), so n! is the largest.
Therefore: n^2 < n^2 log n < n^3 log(log n) < n!