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