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. For example, an application that must protect itself from malicious input will avoid naive implementations of quicksort, which has a worst-case time complexity of N2 despite having one of the fastest average-case time complexities compared to all other sorts.