Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Time complexity classes

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.