Question

Which time complexity grows the slowest as input size increases?

• A. $O(n)$
• B. $O(\log n)$
• C. $O(n^2)$
• D. $O(2^n)$

Hint:

$O(\log n)$ is the complexity of Binary Search. It is so efficient that doubling the input size only adds one additional operation to the total execution time!

Answer 1

The Correct Option is B

Concept: Different algorithms scale differently. Understanding the "Order of Growth" allows us to choose the most efficient solution for large data.
• Logarithmic: $O(\log n)$ increases very slowly.
• Linear: $O(n)$ increases directly with input.
• Polynomial: $O(n^2)$ increases significantly.
• Exponential: $O(2^n)$ becomes unusable very quickly.

Step 1: Comparing specific values for $n = 1024$.
If $n = 1024$: $\log_2(1024) = 10$ operations. $n = 1024$ operations.

Step 2: Analyzing higher-order growth.
Continuing with $n = 1024$: $n^2 \approx 1,000,000$ operations. $2^n \approx \text{a number with over 300 digits.}$

Step 3: Ranking the complexities.
The standard ranking from slowest to fastest growth is: $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$ Logarithmic growth is the slowest among the options provided.