Space and time complexity
Space complexity is a measure of how much memory an algorithm uses, while time complexity is a measure of how long it takes to run.
Time complexity
Time complexity describes how much time an algorithm needs to be complete. The time complexity is usually expressed using the following notations:
Worst case → Big O (O) →
O(n)Best case → Big Ω (Omega) ->
Ω(n)Average case → Big Θ (Theta) ->
Θ(n)
Space complexity
Space complexity described how much space or memory an algorithm needs to be complete. The space complexity is usually expressed using the following notation:
Worst case → Big O (O) →
O(n)
Time and space complexity of search algorithms
Search algorithm
Time / Big-O
Time / Big-Ω
Time / Big-Θ
Space / Big-O
O(log n)
Ω(1)
Θ(log n)
O(1)
O(|V|+|E|)
O(|V|)
O(|V|+|E|)
O(|V|)
O(log n)
Ω(1)
Θ(log n)
O(1)
O(log n)
Ω(1)
Θ(log n)
O(1)
O(log log n)
O(sqrt(n))
O(1)
O(n)
Ω(1)
Θ(n/2)
O(1)
O(m*n)
Links
Last updated