Logarithmic Time Complexity Explained Simply: Understanding O(log n) as a Beginner

Rakibul H. Rabbi

6 min read

·

Sep 5, 2026

--

Listen

Share

Press enter or click to view image in full size

When I first started learning Data Structures and Algorithms, Big O notation felt much more complicated than it actually is.

O(n), O(n²), O(log n), O(n log n)...

At first, they just looked like mathematical formulas.

But after understanding the basic idea behind them, I realized that Big O is mostly about one simple question:

How quickly does the amount of work grow when the input gets bigger?

Today, I want to explain one of the most useful ones:

O(log n) — Logarithmic Time Complexity

I’ll try to explain it without making it unnecessarily mathematical.

First, What Does “log” Actually Mean?

Let’s start with a simple example.

Consider:

log₂(8) = 3

What does that mean?

It means:

2 × 2 × 2 = 8

We multiplied 2 by itself 3 times to get 8.

So:

log₂(8) = 3

Another example:

log₉(81) = 2

Because:

9 × 9 = 81

So the logarithm basically asks:

“What power do I need to raise this number to, to get the target number?”

That’s the mathematical idea.

But for algorithms, there is an even easier way to think about it.

The Easiest Way to Understand O(log n)

Think about repeatedly cutting something in half.

Suppose we start with:

16

Now divide it by 2:

16 → 8

Again:

8 → 4

Again:

4 → 2

Again:

2 → 1

We needed only 4 operations.

So:

log₂(16) = 4

This is the key idea behind logarithmic complexity.

If an algorithm reduces the problem by a constant factor — often half — on every step, it can have O(log n) time complexity.

The example of repeatedly dividing 16 by 2 follows this exact pattern.

Why Is O(log n) So Fast?

Let’s compare two approaches.

Imagine we have 1,000,000 items and we want to find something.

Approach 1 — Check One by One

We might have to check:

1
2
3
4
5
6
...
1,000,000

In the worst case, that’s around:

O(n)

The number of operations grows with the size of the input.

Approach 2 — Keep Cutting the Search Space in Half

Instead, imagine that every step allows us to throw away half of the possibilities.

Something like:

1,000,000
    ↓
500,000
    ↓
250,000
    ↓
125,000
    ↓
62,500
    ↓
...
    ↓
1

We don’t need one million steps.

We only need roughly 20 steps because:

2²⁰ ≈ 1,000,000

That’s the power of logarithmic complexity.

A huge input can be reduced to a very small number of steps.

The Best Example: Binary Search

This is probably the easiest algorithm for understanding O(log n).

Suppose we have a sorted array:

[2, 4, 6, 8, 10, 12, 14, 16, 18]

And we want to find:

14

Instead of starting from the beginning and checking every number, Binary Search looks at the middle.

The middle is:

10

We know:

14 > 10

Because the array is sorted, everything before 10 can be ignored.

Now we only need:

[12, 14, 16, 18]

Again, we check the middle.

We keep eliminating roughly half of the remaining possibilities.

That’s the important part.

Binary search doesn’t search through everything. It keeps reducing the search space.

The source example describes binary search in exactly this way: the search space is reduced by half on each operation, giving logarithmic complexity.

Why Is Binary Search O(log n)?

Let’s imagine there are 16 elements.

After every step:

16
 ↓
8
 ↓
4
 ↓
2
 ↓
1

Only 4 reductions are needed.

Therefore:

log₂(16) = 4

So binary search has:

O(log n)

time complexity.

And this is why sorted data can be extremely powerful.

Sorting gives us information that allows us to eliminate large portions of the search space.

O(n) vs O(log n)

This was one of the things that helped me understand Big O better.

Think of searching for a name in a phone book.

O(n)

You start from the first name:

A
B
C
D
E
...

You check one by one.

That’s roughly:

O(n)

O(log n)

Instead, you open somewhere around the middle.

If the name you’re looking for should come later alphabetically, you ignore the first half.

Then you repeat.

100%
 ↓
50%
 ↓
25%
 ↓
12.5%
 ↓
...

That’s the basic intuition behind:

O(log n)

You are not necessarily doing “less work” in every possible sense.

You are shrinking the problem very quickly.

Why Is the Base Usually 2?

You might wonder:

Why do we keep seeing log₂(n)?

Because many algorithms repeatedly divide something into two parts.

For example:

n → n/2 → n/4 → n/8 → ...

Binary search is a perfect example.

Since the problem is approximately halved at every step, base 2 naturally appears.

In algorithm analysis, base 2 is commonly used for logarithmic complexity.

There is also an important practical point:

For Big O, the exact base of the logarithm usually doesn’t change the overall complexity class.

So you’ll often simply see:

O(log n)

instead of:

O(log₂ n)

What About O(n log n)?

Now we can take the same idea one step further.

You may have already seen:

O(n log n)

This basically combines:

n

and:

log n

Some common sorting algorithms are associated with O(n log n) complexity, including Merge Sort and Heap Sort; the source also discusses Quick Sort in this context.

You don’t need to understand all of the details immediately.

For now, just remember:

O(log n)     → very efficient
O(n)         → grows linearly
O(n log n)   → more work than O(n), but often efficient for sorting
O(n²)        → grows much faster

There Is Also O(log log n)

Yes, it gets even smaller.

We can have:

O(log log n)

For example:

log₂(log₂(256))

First:

log₂(256) = 8

Then:

log₂(8) = 3

So:

log₂(log₂(256)) = 3

The important thing isn’t memorizing the calculation.

Just understand the hierarchy:

log log n
    ↓
log n
    ↓
n
    ↓
n log n
    ↓
n²

Generally, the lower-growing functions scale better as n becomes very large.

The Mental Model I Use

If you’re just starting with algorithms, don’t try to memorize every Big O formula.

Instead, ask yourself:

What happens to the problem after every operation?

If you see:

n → n/2 → n/4 → n/8 → ...

Think:

O(log n)

If you see:

n → n-1 → n-2 → n-3 → ...

Think:

O(n)

If you see a loop inside another loop:

n × n

Think:

O(n²)

This mental model is much easier than trying to memorize formulas.

A Simple Example From Everyday Life

Imagine you’re looking for a particular page in a 1000-page book.

Linear approach

Start from page 1:

1 → 2 → 3 → 4 → 5 → ...

Worst case:

1000 checks

Logarithmic approach

Open around page 500.

If the page you’re looking for is earlier:

1000 → 500

Then:

500 → 250

Then:

250 → 125

And continue.

You’re constantly throwing away half the search space.

That’s the intuition behind logarithmic algorithms.

What Should a Beginner Remember?

If you’re currently learning Data Structures and Algorithms, I wouldn’t try to memorize dozens of complexity types.

Start with these:

O(1)       → Constant
O(log n)   → Logarithmic
O(n)       → Linear
O(n log n) → Linearithmic
O(n²)      → Quadratic

And understand why they behave differently.

Especially:

O(log n)

Remember one sentence:

O(log n) usually means the problem keeps getting significantly smaller — often by half — with each step.

Once this clicks, algorithms like Binary Search become much easier to understand.

And more importantly, Big O stops looking like scary mathematics and starts looking like what it really is:

a way of thinking about how an algorithm scales.

Final Thought

When I first looked at Big O, I thought the goal was to memorize formulas. I don’t think that’s the right way to approach it. The better question is:

“How is my algorithm reducing the problem?”

If the answer is:

“I’m cutting the problem in half again and again.”

You should immediately start thinking:

O(log n)

That’s the idea.

Simple, but extremely important.