Searching Algorithms
Array Search Operations
| Algorithm | Description | Time Average (Θ) | Time Worst (O) |
|---|---|---|---|
| Linear Search | Sequentially checks each element in a list until a match is found. | Θ(n) | O(n) |
| Binary Search | Efficiently locates a target value within a sorted array by repeatedly dividing the search interval in half. | Θ(log n) | O(log n) |
Graph Search Operations
| Algorithm | Description | Time Average (Θ) | Time Worst (O) |
|---|---|---|---|
| Depth-First (DFS) | Traverses as far as possible along each branch before backtracking. | Θ(v + e) | O(v + e) |
| Breadth-First (BFS) | Explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth level. | Θ(v + e) | O(v + e) |
| Bellman-Ford | Finds the shortest path from a single source vertex to all other vertices in a weighted graph, including negative edge weights. | Θ(v × e) | O(v × e) |
| Dijkstra's | Finds the shortest path from a single source vertex to all other vertices in a weighted graph, with non-negative edge weights. | Θ((v + e) log v) | O((v + e) log v) |
| A-Star (A*) | An informed search algorithm that uses a heuristic to estimate the cost of reaching the goal, combining the cost to reach the current node and the estimated cost to reach the goal. | Θ(b ^ d) | O(b ^ d) |
Legend
-
v= Number of vertices -
e= Number of edges -
b= Branching factor -
d= Depth of optimal solution