What is Time Complexity?
In Computer science, there are various problems and several ways to solve each of these problems using different algorithms. These algorithms may have varied approaches, some might be too complex to Implement while some may solve the problem in a lot simpler way than others. It is hard to select a suitable and efficient algorithm out of all that are available. To make the selection of the best algorithm easy, calculation of complexity and time consumption of an algorithm is important this is why time complexity analysis is important, for this asymptotic analysis of the algorithm is done.
There are three cases denoted by three different notations of analysis:
- Big-oh(O) Notation: Denotes the upper bound of any algorithm’s runtime i.e. time is taken by the algorithm in the worst case.
- Big-omega(Ω) Notation: Denotes the best runtime of an algorithm.
- Big-Theta(Θ) notation: Denotes average case time complexity.
How to measure complexities?
Below are some major order of Complexities are:
- Constant: If the algorithm runs for the same amount of time every time irrespective of the input size. It is said to exhibit constant time complexity.
- Linear: If the algorithm runtime is linearly proportional to the input size then the algorithm is said to exhibit linear time complexity.
- Exponential: If the algorithm runtime depends on the input value raised to an exponent then it is said to exhibit exponential time complexity.
- Logarithmic: When the algorithm runtime increases very slowly compared to an increase in input size i.e. logarithm of input size then the algorithm is said to exhibit logarithmic time complexity.
Notation | Complexity |
---|---|
O(1) | Constant |
O(log N) | Logarithmic |
O(N) | Linear time |
O(N * log N) | Log linear |
O(N^2) | Quadratic |
O(N^3) | Cubic |
O(2^N) | Exponential |
O(N!) | Factorial |
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.
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