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	O(log n)	Ω(1)	Θ(log n)	O(1)
Breadth First Search	O(|V|+|E|)			O(|V|)
Depth First Search	O(|V|+|E|)			O(|V|)
Exponential Search	O(log n)	Ω(1)	Θ(log n)	O(1)
Fibonacci Search	O(log n)	Ω(1)	Θ(log n)	O(1)
Interpolation Search	O(log log n)
Jump Search	O(sqrt(n))			O(1)
Linear Search	O(n)	Ω(1)	Θ(n/2)	O(1)
Sublist Search	O(m*n)

Links

• https://www.educative.io/edpresso/time-complexity-vs-space-complexity

• https://levelup.gitconnected.com/time-and-space-complexity-725dcba31902

• https://en.wikipedia.org/wiki/Linear_search

• https://en.wikipedia.org/wiki/Binary_search_algorithm

• https://en.wikipedia.org/wiki/Breadth-first_search

• https://en.wikipedia.org/wiki/Depth-first_search

• https://en.wikipedia.org/wiki/Exponential_search

• https://en.wikipedia.org/wiki/Fibonacci_search_technique

• https://en.wikipedia.org/wiki/Interpolation_search

• https://www.geeksforgeeks.org/jump-search/

• https://www.geeksforgeeks.org/linear-search/

• https://www.geeksforgeeks.org/sublist-search-search-a-linked-list-in-another-list/