The asymptotic complexities of four functions are: f1(n) = 2n f2(n) = n3/2…
2023
The asymptotic complexities of four functions are:
f1(n) = 2n
f2(n) = n3/2
f3(n) = n log n
f4(n) = nlog n
Which option gives the functions in increasing order of asymptotic growth (lowest to highest)?
- A.
f2, f3, f4, f1
- B.
f1, f2, f3, f4
- C.
f3, f2, f4, f1
- D.
f3, f1, f2, f4
Attempted by 234 students.
Show answer & explanation
Correct answer: C
Increasing-order comparison:
f3(n) = n log n grows slower than any fixed polynomial nk where k > 1.
f2(n) = n3/2 is a fixed polynomial.
f4(n) = nlog n grows faster than any fixed polynomial but slower than 2n.
f1(n) = 2n is exponential and grows fastest here.
Order: f3, f2, f4, f1
Final answer: Option C