Which of the given options provides the increasing order of asymptotic…
Which of the given options provides the increasing order of asymptotic complexity of functions \(f1,f2,f3\) and \(f4\)?
f1(n) = 2n
f2(n) = n3/2
f3(n) = n log2 n
f4(n) = nlog2 n
Answer: A. \(f_3, f_2, f_4, f_1\) — Key insight: compare growth rates by taking ratios or logarithms. Compare f3(n)=n log_2 n and f2(n)=n^{3/2}: (n log n)/n^{3/2} = (log n)/n^{1/2} -> 0, so n…
- A.
\(f_3, f_2, f_4, f_1\) - B.
\(f_3, f_2, f_1, f_4\) - C.
\(f_2, f_3, f_1, f_4\) - D.
\(f_2, f_3, f_4, f_1\)
Attempted by 330 students.
Show answer & explanation
Correct answer: A
Key insight: compare growth rates by taking ratios or logarithms.
Compare f3(n)=n log_2 n and f2(n)=n^{3/2}: (n log n)/n^{3/2} = (log n)/n^{1/2} -> 0, so n log_2 n = o(n^{3/2}).
Analyze f4(n)=n^{log_2 n}. Rewrite as f4(n)=2^{(log_2 n)^2}. Since (log_2 n)^2 -> infinity, f4 grows faster than any polynomial n^c (so n^{3/2} = o(n^{log_2 n})).
Compare f4 and f1(n)=2^n: f4(n)=2^{(log_2 n)^2} and (log_2 n)^2 = o(n), so 2^{(log_2 n)^2} = o(2^n). Thus f4 = o(f1).
Conclusion: the functions in increasing asymptotic order are n log_2 n, n^{3/2}, n^{log_2 n}, 2^n (i.e., f3, f2, f4, f1).