Comparing Search and Graph Algorithms
1. Comparing Linear vs Binary Search
| Algorithm | Time Complexity (Avg) | Space Complexity | Requirements | Notes |
|---|---|---|---|---|
| Linear Search | O(n) |
O(1) |
None | Works on unsorted arrays |
| Binary Search | O(log n) |
O(1) |
Sorted array | Must be sorted to function |
Example: Linear Search Implementation
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
const arr = [5, 3, 8, 1, 9];
console.log(linearSearch(arr, 8)); // Output: 2Example: Binary Search Implementation
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
const sortedArr = [1, 3, 5, 8, 9];
console.log(binarySearch(sortedArr, 8)); // Output: 3When to Use Which
- Linear Search: When data is unsorted or small dataset
- Binary Search: When data is sorted and performance matters
2. Comparing Advanced Searches
| Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| Binary Search | O(log n) |
O(1) |
Sorted arrays/vectors |
| Interpolation Search | O(log log n) averageO(n) worst |
O(1) |
Uniformly distributed sorted data |
| Exponential Search | O(log i) where i is index of element |
O(1) |
Unbounded or unknown size arrays |
| Ternary Search | O(log₃ n) |
O(1) |
Sorted arrays with unimodal functions |
| Jump Search | O(√n) |
O(1) |
Sorted arrays with large datasets |
Example: Binary Search Implementation
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Example: Interpolation Search Implementation
function interpolationSearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right && target >= arr[left] && target <= arr[right]) {
let pos = left + Math.floor(((target - arr[left]) / (arr[right] - arr[left])) * (right - left));
if (arr[pos] === target) return pos;
if (arr[pos] < target) left = pos + 1;
else right = pos - 1;
}
return -1;
}Comparison Summary
- Binary Search: Best for sorted arrays, consistent performance
- Interpolation Search: Efficient for uniformly distributed data
- Exponential Search: Ideal when array size is unknown or very large
- Ternary Search: Useful for finding min/max in unimodal functions
- Jump Search: Good for large datasets where memory is limited
3. Comparing String Search Algorithms
| Algorithm | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Naive String Search | O(n*m) |
O(1) |
Checks every position in the text for a match with the pattern. Simple but inefficient for large texts. |
| KMP (Knuth-Morris-Pratt) | O(n+m) |
O(m) |
Preprocesses the pattern to avoid unnecessary character comparisons. Efficient for repeated searches. |
| Boyer-Moore | O(n*m) worst case, O(n/m) average |
O(k) |
Searches from right to left and skips characters based on mismatched characters. Fast in practice for large alphabets. |
| Rabin-Karp | O(n+m) average, O(n*m) worst |
O(1) |
Uses hashing to find a pattern in the text. Useful for multiple pattern searches or when rolling hash is beneficial. |
Example: KMP Algorithm Implementation
function buildLPS(pattern) {
const lps = new Array(pattern.length).fill(0);
let len = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len !== 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
function KMPSearch(text, pattern) {
const lps = buildLPS(pattern);
let i = 0;
let j = 0;
while (i < text.length) {
if (pattern[j] === text[i]) {
i++;
j++;
}
if (j === pattern.length) {
console.log("Found pattern at index " + (i - j));
j = lps[j - 1];
} else if (i < text.length && pattern[j] !== text[i]) {
if (j !== 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
}Example: Boyer-Moore Implementation
function buildBadCharTable(pattern) {
const table = new Array(256).fill(-1);
for (let i = 0; i < pattern.length; i++) {
table[pattern.charCodeAt(i)] = i;
}
return table;
}
function boyerMooreSearch(text, pattern) {
const badCharTable = buildBadCharTable(pattern);
let s = 0;
while (s <= text.length - pattern.length) {
let j = pattern.length - 1;
while (j >= 0 && pattern[j] === text[s + j]) {
j--;
}
if (j < 0) {
console.log("Pattern found at index " + s);
s += (s + pattern.length < text.length) ? pattern.length - badCharTable[text.charCodeAt(s + pattern.length)] : 1;
} else {
s += Math.max(1, j - badCharTable[text.charCodeAt(s + j)]);
}
}
}When to Use Which Algorithm
- Naive: For small texts or when simplicity is preferred over performance.
- KMP: When the pattern is long and repeated searches are expected.
- Boyer-Moore: When the alphabet size is large and the pattern is relatively short.
- Rabin-Karp: For searching multiple patterns or when rolling hash is beneficial.
4. Comparing BFS vs DFS
| Aspect | BFS (Breadth-First Search) | DFS (Depth-First Search) |
|---|---|---|
| Traversal Order | Level-by-level |
Go deep before wide |
| Data Structure Used | Queue |
Stack (or recursion) |
| Memory Usage | Higher (stores all nodes at current level) | Lower (only stores path to current node) |
| Time Complexity | O(V + E) |
O(V + E) |
| Space Complexity | O(V) |
O(V) |
| Use Case Examples | Shortest path in unweighted graphs, level-order traversal | Topological sorting, cycle detection, maze solving |
Example: BFS vs DFS Implementation
const graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
};
// BFS Implementation
function bfs(start, target) {
const queue = [start];
const visited = new Set();
while (queue.length > 0) {
const node = queue.shift();
if (node === target) return true;
if (!visited.has(node)) {
visited.add(node);
queue.push(...graph[node]);
}
}
return false;
}
// DFS Implementation
function dfs(start, target) {
const stack = [start];
const visited = new Set();
while (stack.length > 0) {
const node = stack.pop();
if (node === target) return true;
if (!visited.has(node)) {
visited.add(node);
stack.push(...graph[node]);
}
}
return false;
}
When to Use BFS vs DFS
- BFS: When you need the shortest path in an unweighted graph or want to explore all nodes at a given depth before moving deeper.
- DFS: When exploring all paths from a node, or when memory is constrained and you're looking for any path to a target.
5. Comparing Shortest Path Algorithms
| Algorithm | Description | Time Complexity | Space Complexity | Use Cases |
|---|---|---|---|---|
| Dijkstra's Algorithm | Finds shortest paths from a single source to all other nodes in weighted graphs with non-negative edge weights. | O((V + E) log V) |
O(V) |
Routing protocols, GPS navigation |
| Bellman-Ford Algorithm | Finds shortest paths from a single source in weighted graphs that may have negative edge weights. | O(VE) |
O(V) |
Financial modeling, detecting negative cycles |
| Floyd-Warshall Algorithm | Computes shortest paths between all pairs of nodes in a weighted graph. | O(V^3) |
O(V^2) |
Network routing, transitive closure |
| A* Algorithm | Heuristic-based search algorithm that finds the shortest path between nodes using a heuristic function. | O(b^d) where b is branching factor and d is depth |
O(b^d) |
Pathfinding in games, robotics |
Example: Dijkstra's Algorithm Implementation in JavaScript
function dijkstra(graph, start) {
const distances = {};
const visited = new Set();
const pq = new PriorityQueue();
for (let node in graph) {
distances[node] = node === start ? 0 : Infinity;
}
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
const current = pq.dequeue();
visited.add(current.node);
for (let neighbor in graph[current.node]) {
if (!visited.has(neighbor)) {
const newDistance = distances[current.node] + graph[current.node][neighbor];
if (newDistance < distances[neighbor]) {
distances[neighbor] = newDistance;
pq.enqueue(neighbor, newDistance);
}
}
}
}
return distances;
}Example: Bellman-Ford Algorithm Implementation in JavaScript
function bellmanFord(edges, vertices, source) {
const distances = Array(vertices).fill(Infinity);
distances[source] = 0;
for (let i = 0; i < vertices - 1; i++) {
for (let edge of edges) {
const [u, v, weight] = edge;
if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
}
}
}
return distances;
}Example: Floyd-Warshall Algorithm Implementation in JavaScript
function floydWarshall(graph) {
const n = graph.length;
const dist = Array(n).fill().map(() => Array(n).fill(Infinity));
for (let i = 0; i < n; i++) {
dist[i][i] = 0;
for (let j = 0; j < n; j++) {
if (graph[i][j] !== 0) {
dist[i][j] = graph[i][j];
}
}
}
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}6. Comparing MST Algorithms
| Algorithm | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Kruskal's | O(E log E) |
O(V) |
Uses Union-Find; works with disconnected graphs |
| Prim's (Array-based) | O(V^2) |
O(V) |
Simple implementation; good for dense graphs |
| Prim's (Binary Heap) | O(E log V) |
O(V) |
Better for sparse graphs |
| Prim's (Fibonacci Heap) | O(E + V log V) |
O(V) |
Optimal for sparse graphs; complex to implement |
When to Use Which
- Kruskal's: When the graph is sparse and you want to avoid complex data structures.
- Prim's (Array-based): When the graph is dense and simplicity is preferred.
- Prim's (Binary Heap): When the graph is sparse and performance matters.
- Prim's (Fibonacci Heap): When you need the best theoretical performance and can handle complexity.
Example: Kruskal's MST
const edges = [
{ u: 0, v: 1, weight: 4 },
{ u: 0, v: 2, weight: 2 },
{ u: 1, v: 2, weight: 1 },
{ u: 1, v: 3, weight: 5 }
];
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
let rootX = this.find(x);
let rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) [rootX, rootY] = [rootY, rootX];
this.parent[rootY] = rootX;
if (this.rank[rootX] === this.rank[rootY]) this.rank[rootX]++;
}
}
}
function kruskalMST(n, edges) {
const uf = new UnionFind(n);
const mst = [];
edges.sort((a, b) => a.weight - b.weight);
for (const edge of edges) {
if (uf.find(edge.u) !== uf.find(edge.v)) {
uf.union(edge.u, edge.v);
mst.push(edge);
}
}
return mst;
}
console.log(kruskalMST(4, edges));
// Output: [{ u: 0, v: 2, weight: 2 }, { u: 1, v: 2, weight: 1 }, { u: 1, v: 3, weight: 5 }]
7. Analyzing Graph Algorithm Complexity
| Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity |
|---|---|---|---|---|
| Breadth-First Search (BFS) | O(V + E) |
O(V + E) |
O(V + E) |
O(V) |
| Depth-First Search (DFS) | O(V + E) |
O(V + E) |
O(V + E) |
O(V) |
| Dijkstra's Algorithm | O((V + E) log V) |
O((V + E) log V) |
O((V + E) log V) |
O(V) |
| A* Search | O(b^d) |
O(b^d) |
O(b^d) |
O(b^d) |
| Floyd-Warshall | O(V^3) |
O(V^3) |
O(V^3) |
O(V^2) |
| Johnson's Algorithm | O(V^2 log V + VE) |
O(V^2 log V + VE) |
O(V^2 log V + VE) |
O(V^2) |
Note:
V represents the number of vertices, and E represents the number of edges in the graph.Key Considerations for Graph Algorithm Complexity
- BFS and DFS have the same complexity as they both traverse each vertex and edge once.
- Dijkstra's algorithm uses a priority queue, leading to logarithmic time complexity.
- A* is heuristic-based; its complexity depends on the quality of the heuristic function.
- Floyd-Warshall computes all-pairs shortest paths, making it suitable for dense graphs.
- Johnson's algorithm is efficient for sparse graphs with negative edge weights.
8. Choosing by Graph Properties
Algorithm Selection Based on Graph Characteristics
- Directed vs Undirected: Use directed graph algorithms (e.g., topological sort, Kosaraju's) for directed graphs; undirected algorithms (e.g., Union-Find, BFS/DFS) for undirected graphs.
- Weighted vs Unweighted: Use weighted algorithms (e.g., Dijkstra, Bellman-Ford) for weighted graphs; unweighted algorithms (e.g., BFS) for unweighted graphs.
- Acyclic vs Cyclic: Use acyclic-specific algorithms (e.g., topological sort, DAG shortest path) for directed acyclic graphs; general-purpose algorithms (e.g., Dijkstra, Floyd-Warshall) for cyclic graphs.
- Connected vs Disconnected: Use connected graph algorithms (e.g., BFS, DFS) for connected graphs; disconnected graph algorithms (e.g., multiple BFS/DFS traversals) for disconnected graphs.
| Algorithm | Graph Type | Time Complexity | Use Case |
|---|---|---|---|
| BFS (Breadth-First Search) | Unweighted, Undirected | O(V + E) |
Shortest path in unweighted graphs |
| Dijkstra's Algorithm | Weighted, Directed/Undirected | O((V + E) log V) |
Shortest path in weighted graphs |
| Floyd-Warshall | Weighted, Directed/Undirected | O(V^3) |
All-pairs shortest paths |
| Topological Sort | Directed Acyclic Graph (DAG) | O(V + E) |
Ordering of tasks with dependencies |
| Kosaraju's Algorithm | Directed Graph | O(V + E) |
Strongly connected components |
Note: For dense graphs, Floyd-Warshall may be preferred despite higher complexity due to its simplicity and consistent performance. For sparse graphs, Dijkstra or Bellman-Ford are more efficient.