Question

Which time complexity is considered the fastest (best) among the following?

• A. O(n log n)
• B. O(log n)
• C. O(n²)
• D. O(2ⁿ)

Hint:

Fastest means the function that grows slowest with n. Compare log n, n log n, n squared, and 2 to the n.

Answer 1

The Correct Option is B

Step 1: 'Fastest' means the slowest growing function of the input size n, since that runs quickest for large n.

Step 2: Order the four choices by growth rate:
\[ O(\log n) < O(n \log n) < O(n^2) < O(2^n) \]

Step 3: Logarithmic growth is the smallest here. For example, at \( n = 1024 \), \( \log_2 n = 10 \), while \( n \log n \approx 10240 \), \( n^2 \approx 10^6 \), and \( 2^n \) is astronomically large.

Step 4: So \( O(\log n) \) is the best (fastest) complexity in the list.

Correct option: (B).