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) 

Shortest path by Dijkstra, using a Minheap as priority queue 
Graph with V vertices and E edges  O((V + E) log V) 
O((V + E) log V) 
O(V) 

Shortest path by Dijkstra, using an unsorted array as priority queue 
Graph with V vertices and E edges  O(V^2) 
O(V^2) 
O(V) 

Shortest path by BellmanFord  Graph with V vertices and E edges  O(VE) 
O(VE) 
O(V) 
No comments:
Post a Comment