---
title: "Prefer O(n) or O(log n) algorithm"
subject: "Data Structure and Algorithm"
chapter: 9
key: "semester_4/data_structure_and_algorithm:prefer-on-or-ologn"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/prefer-on-or-ologn
site: BCT Engineering
---

# Prefer O(n) or O(log n) algorithm

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2069 Bhadra, 4 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/prefer-on-or-ologn
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

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?

## 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.

## Answer

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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which algorithm is preferred for large inputs?
   A. O(log n), since it grows far more slowly
   B. O(n), since it is simpler
   C. Either, they are equal
   D. O(n) since log n is larger
   Answer: A. log n << n for large n. (Key point: Preference)

2. For one million items, about how many steps does O(log n) need?
   A. About 1000
   B. About 20
   C. About 500,000
   D. About 1,000,000
   Answer: B. log2(10^6) is about 20. (Key point: Numbers)

3. When might O(n) be faster?
   A. Never
   B. For all large n
   C. For small n or when the O(log n) method has a huge constant or needs sorting first
   D. Only when n is prime
   Answer: C. Big-O hides constants. (Key point: Caution)

4. Which pair is correct?
   A. Binary search O(n); sequential O(log n)
   B. Both O(log n)
   C. Both O(n^2)
   D. Binary search is O(log n); sequential search is O(n)
   Answer: D. Standard search complexities. (Key point: Example)

## Related in Data Structure and Algorithm

- [TOH problem with solution for n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-n-disks-solution) — Data Structure and Algorithm, chapter 5, asked 2×
- [Data types and classification of algorithms](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adata-types-classify-algorithms) — Data Structure and Algorithm, chapter 1
- [AVL delete then insert gives same tree?](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-delete-insert-original) — Data Structure and Algorithm, chapter 6
- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×
- [Recursion, Fibonacci and TOH](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-fibonacci-toh) — Data Structure and Algorithm, chapter 5

## Related in other subjects

- [Multipath inheritance problem and solution](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Amultipath-inheritance-problem) — Object Oriented Programming, chapter 6, asked 2×
- [Linear solution techniques; CG algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asolution-techniques-cg-algorithm) — Computational Techniques in Civil Engineering, chapter 2
- [Dining philosophers problem and solution](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adining-philosophers) — Operating System, chapter 3, asked 2×
- [Adaptive equalization algorithms (any two)](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aadaptive-equalization-algorithms) — Wireless Communication, chapter 5