Algorithms
Algoritms are a set of well-defined instructions to solve a specific problem or perform a computation. Sorting and searching are core aspects and are key types of algorithms. The study of DSA involves a comprehensive understanding of various ways to manage data and process it efficiently using different algorithmic techniques. this is the foundation of: 🚀 Performance 📈 Scalability 😊 User experience 💰 Cost optimization 🏗️ Reliable large-scale systems
The field also covers:
The field also covers:
- Recursion and Backtracking
- Graph Algorithms (e.g. Dijkstra's, Prim's, Kruskal's, maximum flow)
- Dynamic Programming (solving complex problems by breaking them into subproblems)
- Greedy Algorithms (making the locally optimal choice at each stage)
- Bit Manipulation
- String pattern matching
DSA used in real world
| Area | Use Case | Algorithms Used |
|---|---|---|
| Product Engineering / Industry Examples Scenario | E-commerce product search | Fast filtering + sorting (Binary Search, Trees) |
| Product Engineering / Industry Examples Scenario | Fraud detection in finance | Graphs, Dynamic Programming |
| Product Engineering / Industry Examples Scenario | Video streaming (Netflix) | Caching + Efficient Data Transfer |
| Product Engineering / Industry Examples Scenario | Ride-hailing apps (Uber/Ola) | Shortest Path Graphs, Heaps |
| AI / Machine Learning Use | Feature selection | Dynamic Programming |
| AI / Machine Learning Use | Recommendation systems | Graph algorithms |
| AI / Machine Learning Use | Clustering & search | Trees (KD-Trees), Hashing |
| Internet & System-Level Use System Component | Network routing | Graphs |
| Internet & System-Level Use System Component | Cache memory (fast retrieval) | Hash Maps, Queues (LRU) |
| Internet & System-Level Use System Component | Operating systems CPU scheduling | Queues, Heaps |
| Internet & System-Level Use System Component | Data compression (ZIP, media) | Huffman Trees |
| Internet & System-Level Use System Component | Load balancers | Hashing + Queues |
| Everyday Applications Use Case | Contacts search in phone | Hash Tables, Trees |
| Everyday Applications Use Case | GPS shortest route (Google Maps) | Graph Algorithms (Dijkstra) |
| Everyday Applications Use Case | Autocomplete & Spellcheck | Tries, Hash Maps |
| Everyday Applications Use Case | Social media feed ranking | Heaps, Graphs, Dynamic Programming |
Sorting algorithms comparison:
| Name | Time Complexity | Space Complexity | Stablility | ||
|---|---|---|---|---|---|
| Best Case | Average Case | Worst Cases | Worst Case | ||
| Bubble Sort | O(N) | O(N^2) | O(N^2) | O(1) | Stable |
| Selection Sort | O(N^2) | O(N^2) | O(N^2) | O(1) | Unstable |
| Insertion Sort | O(N) | O(N^2) | O(N^2) | O(1) | Stable |
| Quick Sort | O(N log N) | O(N log N) | O(N^2) | O(N) | Unstable |
| Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) | Stable |
| Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) | Unstable |
Search algorithms comparison:
| Name | Prerequisite | Time Complexity | Space Complexity | Stablility | ||
|---|---|---|---|---|---|---|
| Best Case | Average Case | Worst Cases | Worst Case | |||
| Linear | O(1) | O(N) | O(N) | O(1) | Not applicable as it doesn't reorder elements based on equal values. | |
| Binary | Requires a sorted array. | O(1) | O(log N) | O(log N) | O(1) - Iterative, O(log N) - Recursive | Not applicable |
| BFS | O(V+E) | O(V+E) | O(V+E) | O(V) | Not Stable | |
| DFS | O(V+E) | O(V+E) | O(V+E) | O(H) | Stable for finding connected components | |
| Jump | O(√N) | O(√N) | O(√N) | O(1) | Not applicable | |
| Interpolation | Requires a sorted array with uniformly distributed elements. | O(log log N) | O(N) | O(1) | Not applicable | |
NotationsO(1) - Constant Time and Space: The time and space taken is independent of the input size (e.g., accessing an element in an array by its index).O(N) - Linear Time and Space: The time and space taken grows proportionally to the input size (e.g., iterating through an array).O(log N) - Logarithmic Time: The time taken increases slowly as the input size grows (e.g., binary search).O(N log N) - Log-linear Time: The time taken grows slightly faster than linear (e.g., efficient sorting algorithms like Merge Sort).O(N^2) - Quadratic Time: The time taken grows proportionally to the square of the input size (e.g., nested loops).O(2^N) - Exponential Time: The time taken grows very rapidly with the input size, making it impractical for large inputs.O(V+E): The time complexity required to visit every vertex (V) and traverse every edge (E) in the graph exactly onceO(V): The time or space complexity is directly proportional to the number of vertices (nodes)O(H): The space taken grows proportionally to the height of the search tree or graph