For indepth understanding of Data Structure and Algorithm concepts refer :
1) INTRODUCTION TO ALGORITHMS by Coremen Introduction to Algorithms, 3rd Edition From flipkart.com
Introduction to Algorithms, 3rd Edition From amazon.com
Introduction to Algorithms from amazon.in
2) DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron  DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron from flipkart.com
Data Structures Using C and C++ (2nd Edition) from amazon.com
Data Structures Using C and C++ from amazon.in
1) INTRODUCTION TO ALGORITHMS by Coremen Introduction to Algorithms, 3rd Edition From flipkart.com
Introduction to Algorithms, 3rd Edition From amazon.com
Introduction to Algorithms from amazon.in
2) DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron  DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron from flipkart.com
Data Structures Using C and C++ (2nd Edition) from amazon.com
Data Structures Using C and C++ from amazon.in
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