This post discusses various algorithmic time complexities and their practical examples.

O(1) - Constant Time

An algorithm that runs the same no matter what the input exemplifies constant time complexity, returning identical results regardless of input size.

O(log n) - Logarithmic Time

Binary search trees and binary search algorithms demonstrate logarithmic efficiency. A balanced binary search tree requires traversing one node per layer, with only log(n) total layers. Binary search divides an ordered array repeatedly, requiring at most log(n) divisions.

O(n) - Linear Time

Linear search algorithms checking each element sequentially represent linear time complexity. Linked list access operations also exhibit O(n) behavior due to lack of random access support.

O(n log n) - Linearithmic Time

Merge sort exemplifies this efficiency class. The algorithm “breaks up an array into two halves, sorts those two halves by recursively calling itself on them, and then merging the result back” yielding O(n log n) overall complexity.

O(n²) - Quadratic Time

Selection sort and comparable algorithms operate within polynomial time, representing reasonable but less efficient solutions.

O(2ⁿ) - Exponential Time

Exponential algorithms address difficult problems like factoring large binary numbers. Trial-and-error approaches require “twice as many tests” per additional digit, demonstrating impractical scalability.

Source: cprogramming.com