One of my friend was ask to devise an algorithm to search a number on a rotated sorted array. Well, we can always do a linear search. But that cannot be optimal we are neglecting the fact that the array was once sorted. The array is still sorted but has been rotated at some point. So, if we could find the rotation point, we could still use binary search to find the number.
Showing posts with label Searching. Show all posts
Showing posts with label Searching. Show all posts
Saturday, 9 November 2013
Playing with Big O - Complexity of different searching and sorting algorithm
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) |
||
Subscribe to:
Posts (Atom)