Time Complexity

There are different measurements of the speed of any given algorithm. Given an input size of N, they can be described as follows:

NameSpeedDescriptionFormulaExample
factorial timeslowertakes an amount of time proportional to N raised to the Nth power N! Brute force solution to Traveling Salesman Problem
exponential timeslowtakes an amount of time proportional to a constant raised to the Nth power KN Brute force solution to Rubik's Cube
polynomial timefasttakes an amount of time proportional to N raised to some constant power NK Comparison sorts (bubble, insertion, selection sort)
linearithmic timefastertakes an amount of time between linear and polynomial N * log(N) The Linear logarithmic sorts (quicksort, heapsort, mergesort)
linear timeeven fastertakes an amount of time directly proportional to N K * N Iterating through an array
logarithmic timemuch fastertakes an amount of time proportional to the logarithm of N K * log(N) Binary Search
constant timefastesttakes a fixed amount of time, no matter how large the input is K Array index lookup

Complexity Analysis

A given operation can have different time complexities with different orders/sets of input. The different methods of time complexity analysis are as follows:

NameDescriptionExample
best-caseA case where the operation executes as fast as it possibly can Bubblesort has a best-case time complexity of N.
average-caseA case where the operation executes in a time comparable to the majority of possible cases Quicksort has an average-case time complexity of N * log(N)
worst-caseA case where the operation executes as slowly as it possibly can Quicksort has a worst-case time complexity of N2
amortized worst-caseThe average worst-case taken over an infinite number of inputs vector::push_back() has an amortized worst-case time complexity of K (constant time)

Choosing the right algorithm depends upon which cases you expect your application to encounter.