- 2069 Bhadra · 4 marks
Prefer O(n) or O(log n) algorithm
Short answer
Prefer the O(log n) algorithm because its steps grow far more slowly than O(n) as input size increases. For large n, O(log n) is vastly faster; for very small n, constant factors might make O(n) comparable.
If you have two different algorithms for the solution to same problem with O(n) and O(log(n)), which one would you prefer and why?
I would prefer the O(log n) algorithm.
Reason: log n grows far more slowly than n, so the O(log n) algorithm needs much less time as the input grows.
| n | Steps for O(log n) (log₂ n) | Steps for O(n) (n) |
|---|---|---|
| 10 | 3.3 | 10 |
| 1,000 | 10 | 1,000 |
| 1,000,000 | about 20 | 1,000,000 |
For one million items, O(n) needs about a million steps, while O(log n) needs about 20. Example: binary search is O(log n) and sequential search is O(n).
Caution: big-O hides constants. For very small n, or when the O(log n) method has a very large constant or needs extra work (such as sorting the data first), the O(n) method can be faster. For large inputs, O(log n) always wins eventually.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- TOH problem with solution for n disks · Data Structure and Algorithm, chapter 5 · asked 2×
- Data types and classification of algorithms · Data Structure and Algorithm, chapter 1
- AVL delete then insert gives same tree? · Data Structure and Algorithm, chapter 6
- Recursion properties, Fibonacci, TOH algorithm · Data Structure and Algorithm, chapter 5
- TOH algorithm and recursion tree · Data Structure and Algorithm, chapter 5 · asked 2×
- Recursion, Fibonacci and TOH · Data Structure and Algorithm, chapter 5
- Multipath inheritance problem and solution · Object Oriented Programming, chapter 6 · asked 2×
- Linear solution techniques; CG algorithm · Computational Techniques in Civil Engineering, chapter 2
- Dining philosophers problem and solution · Operating System, chapter 3 · asked 2×
- Adaptive equalization algorithms (any two) · Wireless Communication, chapter 5