While preparing for interview, I have wasted a lot of my time on summing down the best, average and worst case complexity of different searching and sorting algorithms. To save you guys from going through same pain, I am posting my work here. So, enjoy this cheat sheet while preparing for interview.
Searching
| Algorithm | Data Structure | Time Complexity | Space Complexity | |||
|---|---|---|---|---|---|---|
| Average | Worst | Worst | ||||
| Depth First Search (DFS) | Graph of |V| vertices and |E| edges | - |
O(|E| + |V|) |
O(|V|) |
||
| Breadth First Search (BFS) | Graph of |V| vertices and |E| edges | - |
O(|E| + |V|) |
O(|V|) |
||
| Binary search | Sorted array of n elements | O(log(n))
|
O(log(n))
|
O(1)
|
||
| Linear (Brute Force) | Array | O(n) |
O(n) |
O(1) |
||
