Introduction

In algorithm analysis, lg N usually means log2 N, which is the logarithm of N base 2. It appears often because many algorithms repeatedly split a problem into two roughly equal parts, so the number of rounds grows like the number of times you can divide by two before reaching 1.

Why Base 2 Shows Up So Often

Binary search is the standard example. Each comparison cuts the search space roughly in half, so the total number of steps is proportional to log2 N.

For a sorted array of size 16, the search path looks like this:

• start with 16 candidates
• then 8
• then 4
• then 2
• then 1

That took four halvings, so the cost is about log2 16 = 4.

A small Python demonstration is:

1def binary_search_steps(n):
2    steps = 0
3    while n > 1:
4        n //= 2
5        steps += 1
6    return steps
7
8print(binary_search_steps(16))
9print(binary_search_steps(1024))

This prints 4 and 10, matching the idea that lg 16 = 4 and lg 1024 = 10.

lg N Versus log N

Authors are not always consistent with notation. In many algorithms texts:

• 'lg N means log2 N'
• 'ln N means natural logarithm, base e'
• 'log N may mean base 2, base 10, or an unspecified base depending on context'

In asymptotic complexity, the exact base usually does not matter for Big O notation because logarithms of different constant bases differ only by a constant factor.

For example:

• 'log2 N'
• 'log10 N'
• 'ln N'

all describe the same complexity class in Big O terms. So O(log N) and O(lg N) are treated as the same growth rate unless the author is being numerically precise.

Where You See lg N in Practice

You will commonly see lg N or logarithmic running time in:

• binary search
• balanced binary search trees
• heap operations such as insert and extract
• divide-and-conquer algorithms with halving structure

Consider heap insertion. A new value may need to move up one level at a time, and a heap with N elements has height about lg N. That is why insertion and removal are typically O(lg N).

Do Not Confuse lg N With lg* N

A frequent source of confusion is the separate notation lg* N, pronounced "log star N". That is a different function altogether. lg* N counts how many times you apply base-2 logarithm before the value becomes at most 1.

So these are different ideas:

• 'lg N means one base-2 logarithm'
• 'lg* N means repeated logarithm count'

If an algorithm text says O(lg N), it means ordinary logarithmic growth, not the much slower-growing log-star function.

Why Logarithmic Growth Is Considered Fast

Logarithmic growth scales very gently. Doubling the input size does not double the cost. It adds only a constant amount of extra work.

For example:

• 'lg 1,024 = 10'
• 'lg 1,048,576 = 20'
• 'lg 1,073,741,824 = 30'

That is why logarithmic algorithms remain efficient even for very large inputs. The running time increases, but much more slowly than linear or quadratic algorithms.

Common Pitfalls

The biggest mistake is assuming lg N means log10 N because that is what some calculators display by default. In algorithm texts, lg almost always means base 2.

Another mistake is worrying too much about the exact logarithm base when working in Big O notation. For complexity classes, constant base changes do not alter the asymptotic category.

Developers also often mix up lg N and lg* N. Those are related notations, but they describe very different growth rates.

Finally, remember that logarithmic complexity usually depends on a problem structure that shrinks multiplicatively. If an algorithm reduces the problem by one item at a time, that is not O(lg N).

Summary

• 'lg N usually means log2 N in algorithm analysis.'
• It appears naturally when an algorithm repeatedly halves the problem size.
• In Big O notation, the exact logarithm base differs only by a constant factor.
• 'lg N is different from lg* N, which is the log-star function.'
• Logarithmic algorithms scale very well because the cost grows slowly as input size increases.