Different Types of Logarithmic Complexities
Now that we know what is a logarithm, let’s deep dive into different types of logarithmic complexities that exists, such as:
Simple Log Complexity (Loga b)
Simple logarithmic complexity refers to log of b to the base a. As mentioned, it refers to the time complexity in terms of base a. In design and analysis of algorithms, we generally use 2 as the base for log time complexities. The below graph shows how the simple log complexity behaves.
Simple Log Complexity (Log(a) b)
There are several standard algorithms that have logarithmic time complexity:
- Merge sort
- Binary search
- Heap sort
Double Logarithm (log log N)
Double logarithm is the power to which a base must be raised to reach a value ‘x’ such that when the base is raised to a power ‘x’ it reaches a value equal to given number.
Double Logarithm (log log N)
Example:
logarithm (logarithm (256)) for base 2 = log2(log2(256)) = log2(8) = 3.
Explanation: 28 = 256, Since 2 needs to be raised to a power of 8 to give 256, Thus logarithm of 256 base 2 is 8. Now 2 needs to be raised to a power of 3 to give 8 so log2(8) = 3.
N logarithm N (N * log N)
N*logN complexity refers to product of N and log of N to the base 2. N * log N time complexity is generally seen in sorting algorithms like Quick sort, Merge Sort, Heap sort. Here N is the size of data structure (array) to be sorted and log N is the average number of comparisons needed to place a value at its right place in the sorted array.
N * log N
logarithm2 N (log2 N)
log2 N complexity refers to square of log of N to the base 2.
log2 N
N2 logarithm N (N2 * log N)
N2*log N complexity refers to product of square of N and log of N to the base 2. This Order of time complexity can be seen in case where an N * N * N 3D matrix needs to be sorted along the rows. The complexity of sorting each row would be N log N and for N rows it will be N * (N * log N). Thus the complexity will be N2 log N,
N2 * log N
N3 logarithm N (N3 log N)
N3*log N complexity refers to product of cube of N and log of N to the base 2. This Order of time complexity can be seen in cases where an N * N matrix needs to be sorted along the rows. The complexity of sorting each row would be N log N and for N rows it will be N * (N * log N) and for N width it will be N * N * (N log N). Thus the complexity will be N3 log N,
N3 log N
logarithm √N (log √N)
log √N complexity refers to log of square root of N to the base 2.
log √N
What is Logarithmic Time Complexity? A Complete Tutorial
Logarithmic time complexity is denoted as O(log n). It is a measure of how the runtime of an algorithm scales as the input size increases. In this comprehensive tutorial. In this article, we will look in-depth into the Logarithmic Complexity. We will also do various comparisons between different logarithmic complexities, when and where such logarithmic complexities are used, several examples of logarithmic complexities, and much more. So let’s get started.
What is Logarithmic Time Complexity
Table of Content
- What is a Logarithm?
- What is Complexity Analysis?
- What is Space Complexity?
- What is Time Complexity?
- How to measure complexities?
- What is a Logarithm?
- Different Types of Logarithmic Complexities
- Simple Log Complexity (Log a)
- Double Logarithm (log log N)
- N logarithm N (N * log N)
- logarithm^2 N (log^2 N)
- N^2 logarithm N (N^2 * log N)
- N^3 logarithm N (N^3 log N)
- logarithm √N (log √N)
- Examples To Demonstrate Logarithmic Time Complexity
- Practice Problems for Logarithmic Time Complexity
- Comparison of various Logarithmic Time Complexities
- Frequently Asked Questions(FAQ’s) on Logarithmic Time Complexity
- Conclusion
Contact Us