Understanding Logarithmic Time Complexity in Big O Notation

What Does ( log n ) Mean in Big O Notation?

In Big O notation, ( log n ) typically refers to the logarithm of ( n ), which is used to describe the time complexity of an algorithm. The logarithm in Big O notation usually has a base of 2 (binary logarithm, ( log2 n )), but in Big O notation, the base of the logarithm is often omitted because logarithms of different bases differ only by a constant factor (and Big O notation focuses on asymptotic behavior, ignoring constant factors).

Key Points about ( log n ) in Big O Notation

1. Logarithmic Complexity: Algorithms with a time complexity of ( O(log n) ) grow very slowly as ( n ) increases. Examples include binary search and certain balanced tree operations.

2. Common Logarithms:

   • ( log2 n ) (binary logarithm): Common in computer science because of binary systems.

   • ( log10n ) (common logarithm): Occasionally used but less common in algorithm analysis.

   • ( ln n ) (natural logarithm, base ( e )): Also used in some contexts, especially in mathematical analysis.

3. Change of Base Formula: The change of base formula ( loga n = frac{logb n}{logb a} ) shows that logarithms of different bases differ by a constant factor (( logb a )), which is why the base is often omitted in Big O notation.

Example

• Binary Search: The time complexity is ( O(log n) ) because the algorithm repeatedly divides the search interval in half.

Comparison with Other Complexities

• Constant Time: ( O(1) )

• Linear Time: ( O(n) )

• Linearithmic Time: ( O(nlog n) )

• Quadratic Time: ( O(n^2) )

• Exponential Time: ( O(2^n) )

Logarithmic time complexity is highly efficient for large input sizes compared to linear or polynomial time complexities.