Time complexity classes provide a framework for analyzing and categorizing the efficiency of algorithms based on their running time as a function of the input size.
Some common time complexity classes and their descriptions:
1. Constant Time: O(1)
- The algorithm’s running time is constant, regardless of the input size.
- The algorithm takes the same amount of time to execute, regardless of the input’s magnitude.
2. Logarithmic Time: O(log n)
- The algorithm’s running time increases logarithmically with the input size.
- As the input size increases, the running time grows, but at a decreasing rate.
- Algorithms with logarithmic time complexity often divide the input in half at each step, such as binary search on a sorted array.
3. Linear Time: O(n)
- The algorithm’s running time increases linearly with the input size.
- As the input size grows, the running time grows at the same rate.
- Algorithms with linear time complexity typically iterate once through the entire input, such as linear search in an unsorted list.
4. Linearithmic Time: O(n log n)
- The algorithm’s running time increases in proportion to n multiplied by the logarithm of n.
- It is commonly seen in efficient sorting algorithms like merge sort and quicksort.
- Algorithms with linearithmic time complexity have a better performance than quadratic time complexity but worse than linear time complexity.
5. Quadratic Time: O(n2)
- The algorithm’s running time increases quadratically with the input size.
- As the input size increases, the running time grows exponentially.
- Algorithms with quadratic time complexity typically involve nested loops, such as bubble sort and selection sort.
6. Exponential Time: O(2n)
- The algorithm’s running time grows exponentially with the input size.
- As the input size increases, the running time grows very rapidly.
- Algorithms with exponential time complexity are highly inefficient and impractical for large inputs, such as generating all subsets or permutations of a set.