> For the complete documentation index, see [llms.txt](https://nielslange.gitbook.io/developer-toolbox/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nielslange.gitbook.io/developer-toolbox/algorithms/space-and-time-complexity.md).

# 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 |
| -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------- | ------------ | ------------ | ------------- |
| [Binary Search](/developer-toolbox/algorithms/search-algorithms/binary-search.md)                                                                                    | `O(log n)`       | `Ω(1)`       | `Θ(log n)`   | `O(1)`        |
| [Breadth First Search](/developer-toolbox/algorithms/search-algorithms/breadth-first-search.md)                                                                      | `O(\|V\|+\|E\|)` |              |              | `O(\|V\|)`    |
| [Depth First Search](/developer-toolbox/algorithms/search-algorithms/depth-first-search.md)                                                                          | `O(\|V\|+\|E\|)` |              |              | `O(\|V\|)`    |
| [Exponential Sear](/developer-toolbox/algorithms/search-algorithms/exponential-search.md)[ch](/developer-toolbox/algorithms/search-algorithms/exponential-search.md) | `O(log n)`       | `Ω(1)`       | `Θ(log n)`   | `O(1)`        |
| [Fibonacci Search](/developer-toolbox/algorithms/search-algorithms/fibonacci-search.md)                                                                              | `O(log n)`       | `Ω(1)`       | `Θ(log n)`   | `O(1)`        |
| [Interpolation Search](/developer-toolbox/algorithms/search-algorithms/interpolation-search.md)                                                                      | `O(log log n)`   |              |              |               |
| [Jump Search](/developer-toolbox/algorithms/search-algorithms/jump-search.md)                                                                                        | `O(sqrt(n))`     |              |              | `O(1)`        |
| [Linear Search](https://codenex.wordpress.com/2021/01/24/developer-toolbox-%e2%86%92-linear-search/)                                                                 | `O(n)`           | `Ω(1)`       | `Θ(n/2)`     | `O(1)`        |
| [Sublist Search](/developer-toolbox/algorithms/search-algorithms/sublist-search.md)                                                                                  | `O(m*n)`         |              |              |               |

### Links

* [https://www.educative.io/edpresso/time-complexity-vs-space-complexity](https://href.li/?https://www.educative.io/edpresso/time-complexity-vs-space-complexity)
* [https://levelup.gitconnected.com/time-and-space-complexity-725dcba31902](https://href.li/?https://levelup.gitconnected.com/time-and-space-complexity-725dcba31902)
* [https://en.wikipedia.org/wiki/Linear\_search](https://href.li/?https://en.wikipedia.org/wiki/Linear_search)
* [https://en.wikipedia.org/wiki/Binary\_search\_algorithm](https://href.li/?https://en.wikipedia.org/wiki/Binary_search_algorithm)
* [https://en.wikipedia.org/wiki/Breadth-first\_search](https://href.li/?https://en.wikipedia.org/wiki/Breadth-first_search)
* [https://en.wikipedia.org/wiki/Depth-first\_search](https://href.li/?https://en.wikipedia.org/wiki/Depth-first_search)
* [https://en.wikipedia.org/wiki/Exponential\_search](https://href.li/?https://en.wikipedia.org/wiki/Exponential_search)
* [https://en.wikipedia.org/wiki/Fibonacci\_search\_technique](https://href.li/?https://en.wikipedia.org/wiki/Fibonacci_search_technique)
* [https://en.wikipedia.org/wiki/Interpolation\_search](https://href.li/?https://en.wikipedia.org/wiki/Interpolation_search)
* [https://www.geeksforgeeks.org/jump-search/](https://href.li/?https://www.geeksforgeeks.org/jump-search/)
* [https://www.geeksforgeeks.org/linear-search/](https://href.li/?https://www.geeksforgeeks.org/linear-search/)
* [https://www.geeksforgeeks.org/sublist-search-search-a-linked-list-in-another-list/](https://href.li/?https://www.geeksforgeeks.org/sublist-search-search-a-linked-list-in-another-list/)