Which growth rate is the slowest for large values of n?
Correct answer C. O(log n)
Explanation
Ordered from slowest to fastest growth, these are O(log n), O(√n), O(n) and O(n log n). A logarithm grows extremely slowly: doubling n adds only one to log₂ n. The square root may look small, but for n equal to one million √n is 1000 while log₂ n is about 20. Algorithms such as binary search achieve logarithmic time.
Answer checked How we write and check questions
Discussion