Arrange the following complexity of the algorithm in ascending order. O(2ⁿ),…
2021
Arrange the following complexity of the algorithm in ascending order. O(2ⁿ), O(n), O(log₂ n), O(n log₂ n), O(n²)
- A.
O(log₂ n), O(n), O(n log₂ n), O(n²), O(2ⁿ)
- B.
O(n), O(log₂ n), O(n log₂ n), O(n²), O(2ⁿ)
- C.
O(n), O(n²), O(log₂ n), O(n log₂ n), O(2ⁿ)
- D.
O(log₂ n), O(n log₂ n), O(n), O(n²), O(2ⁿ)
Attempted by 209 students.
Show answer & explanation
Correct answer: A
As nnn becomes very large:
Logarithmic functions grow the slowest.
Linear functions grow faster than logarithmic.
nlogn grows faster than linear but slower than quadratic.
Quadratic growth outpaces all polynomial terms listed above.
Exponential growth eventually dwarfs everything else.