What is Time Complexity?
Big-O Time Complexities (Fastest to Slowest)
Constant Time
O(1)
Constant Running Time
Example Algorithms
Finding the median value in a sorted array of numbers
Logarithmic Time
O(log n)
Operations grow proportionally to the logarithm of the input size
10 elements take x time
100 elements take 2x time
1000 elements take 4x time
10000 elements take 16x time
Example Algorithms
Binary Search Time
Linear Time
O(n)
Run time grows linearly to the number
Example Algorithms
Finding the smallest or largest item in an unsorted array
Kadane’s algorithm
Linear Search
Linearithmic Time
O(n log n)
“The worst of the best time complexities”
Combination of linear time and logarithmic time
Floats around linear time until input reaches an advanced size
Example Algorithms
The best comparison sort algorithm
Quadratic Time
O(n^2)
Exponential Time
O(2^n)
Factorial Time
O(n!)