Big O notation

The T(n) time function represents the algorithm complexity based on Big O notation. T(n) = O(n) states that an algorithm has a linear time complexity. Using Big O notation, the constant time, linear time, logarithmic time, cubic time, and quadratic time complexity are different complexity types for an algorithm.

Linear time, O(n), is used as a measure of complexity in scenarios such as linear search, traversing, and finding the minimum and maximum number of array elements. ArrayList and queue are data structures that have these methods. An algorithm that has logarithmic time, O(log n), is a binary search in a tree data structure. Bubble sort, selection sort, and insertion sort algorithms have complexity of quadratic time, O(n2). Big Omega Ω and big Theta Θ are notations for the lower and upper bounds for a particular algorithm.

The worst case, best case, average case, and amortized run-time complexity is used for analysis of algorithms. Amortized run-time complexity is referred to as 2n. Asymptotically, it will tend to O(1).

Big O notation is also used to determine how much space is consumed by the algorithm. This helps us find the best and worst case scenarios, relative to space and time.

Let's take a look at linear complexity in the next section.