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.
Last updated
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.
Last updated
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 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)
| 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)