Introduction

O(n) and O(log n) describe how an algorithm's work grows as the input grows. In general, O(log n) scales better than O(n), but the comparison only makes sense when both algorithms solve the same problem under compatible assumptions.

What O(n) Means

O(n) is linear time. If the input size roughly doubles, the amount of work also roughly doubles. The classic example is scanning an unsorted list until you either find the target or reach the end.

1def contains_linear(values, target):
2    for value in values:
3        if value == target:
4            return True
5    return False
6
7
8print(contains_linear([8, 3, 5, 1], 5))

In the worst case, the algorithm touches every element once. That is why the growth is proportional to n.

Linear time is not inherently bad. It is often the natural lower bound when you genuinely need to inspect every item. For example, computing a sum over an array or checking whether any element matches a condition is usually O(n) because each value has to be examined at least once.

What O(log n) Means

O(log n) is logarithmic time. The algorithm reduces the remaining search space by a constant factor at each step, often by half.

Binary search is the standard example:

1def contains_binary(values, target):
2    low = 0
3    high = len(values) - 1
4
5    while low <= high:
6        mid = (low + high) // 2
7        guess = values[mid]
8
9        if guess == target:
10            return True
11        if guess < target:
12            low = mid + 1
13        else:
14            high = mid - 1
15
16    return False
17
18
19print(contains_binary([1, 3, 5, 8, 10, 12], 8))

This works only because the input is sorted. After each comparison, half the remaining candidates can be discarded. That repeated halving is what gives the logarithmic growth.

Why O(log n) Grows So Much More Slowly

The practical difference becomes obvious at large sizes. For one million items:

• a linear search may need up to one million checks
• a binary search needs about twenty checks because log2(1,000,000) is close to 20

That is why O(log n) is usually considered better asymptotically. Each time the input doubles, a logarithmic algorithm adds only a tiny amount of extra work.

The base of the logarithm is usually omitted in Big O notation because changing the base only changes the result by a constant factor. In Big O terms, constant multipliers are ignored, so O(log2 n) and O(log10 n) are both written as O(log n).

"Better" Depends on the Setup Cost

People often stop at "logarithmic is better than linear," but that is incomplete. Binary search only applies when the data is already sorted and randomly accessible. If the data is unsorted, you may need to sort it first.

1values = [8, 3, 5, 1, 10, 12]
2values.sort()  # O(n log n)
3found = contains_binary(values, 8)
4print(found)

If you only need one lookup on a short unsorted list, a simple linear scan may be more sensible than paying the sorting cost first. If you need thousands of lookups, preprocessing into a sorted structure can easily be worth it.

So the right question is not only "which complexity class is smaller?" It is also:

• what assumptions does the algorithm require
• what preprocessing cost exists
• how many times will the operation run

Complexity Classes Compare Growth, Not Exact Runtime

Big O is about growth rate, not exact timing. A carefully optimized O(n) algorithm can beat a badly implemented O(log n) algorithm on small inputs. Constant factors, cache friendliness, memory layout, and implementation details still matter.

That does not invalidate Big O. It just means complexity tells you how performance scales, not how many milliseconds a specific program will take on your machine for a specific input size.

A useful engineering habit is to use Big O for structural reasoning and actual measurements for real-world tuning. The complexity class tells you whether the approach is likely to scale. Benchmarks tell you whether the implementation is acceptable now.

Data Structures Often Decide the Complexity

The complexity you can achieve often depends on the data structure. An unsorted list naturally leads to O(n) search. A sorted array enables O(log n) search. A hash table often gives average-case constant-time lookup.

That means algorithm analysis and data-structure choice are tightly connected. You are not usually choosing between naked O(n) and naked O(log n). You are choosing between different problem setups and data representations that make those complexities possible.

Common Pitfalls

One common mistake is thinking O(log n) means "slightly smaller than O(n)." For large inputs, the gap is dramatic because the growth models are fundamentally different.

Another pitfall is applying a logarithmic algorithm without satisfying its assumptions. Binary search on unsorted data is incorrect, no matter how attractive the complexity looks.

A third issue is ignoring preprocessing cost. Sorting data or building a search structure may be worthwhile for many queries and wasteful for one quick operation.

Finally, remember that Big O ignores constant factors. That is useful for scaling analysis, but it does not automatically predict the fastest implementation for small inputs.

Summary

• 'O(n) means work grows roughly in proportion to the input size.'
• 'O(log n) means work grows by repeatedly shrinking the problem by a constant factor.'
• Asymptotically, O(log n) scales better than O(n).
• The better practical choice depends on assumptions such as sorted data, preprocessing cost, and how many times the operation will be performed.
• Big O describes growth, not exact runtime on a specific machine.