हिंदी में: किसी समस्या को हल करने के क़दम-दर-क़दम तरीके और उनकी स्पीड कैसे मापें।
What is an algorithm?
An algorithm is a finite, well-defined sequence of steps that solves a problem. A good algorithm is correct, terminates, and uses as little time and memory as possible.
Analysing algorithms: asymptotic notation
- Big-O (O) – upper bound (worst-case growth).
- Omega (Ω) – lower bound.
- Theta (Θ) – tight bound.
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort, heap sort |
| O(n²) | Quadratic | Bubble sort, insertion sort |
| O(2ⁿ) | Exponential | Naive recursive subset problems |
| O(n!) | Factorial | Brute-force travelling salesman |
Searching
- Linear search: check each element — O(n), works on unsorted data.
- Binary search: repeatedly halve a sorted array — O(log n).
def binary_search(a, x):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == x:
return mid
if a[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return -1
Sorting
| Algorithm | Best | Average | Worst | Extra space | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
A stable sort keeps equal elements in their original order. Any comparison-based sort needs at least Ω(n log n) comparisons in the worst case.
Design techniques
Divide and conquer
Split the problem, solve the parts recursively, combine the answers. Examples: merge sort, quick sort, binary search. Recurrences such as T(n) = 2T(n/2) + n are solved with the Master Theorem, giving O(n log n).
Greedy
Make the best local choice at each step. Works when the problem has the greedy-choice property. Examples: activity selection, fractional knapsack, Huffman coding, Prim’s and Kruskal’s minimum spanning tree, Dijkstra’s shortest path.
Dynamic programming (DP)
Used when a problem has overlapping subproblems and optimal substructure. Store answers to subproblems (memoization or tabulation) instead of recomputing them. Examples: Fibonacci, 0/1 knapsack, longest common subsequence, matrix chain multiplication, Floyd–Warshall.
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time instead of O(2^n)
Backtracking
Build a solution step by step and undo a step as soon as it cannot lead to a valid answer. Examples: N-Queens, Sudoku, generating permutations.
Graph algorithms
| Algorithm | Purpose | Time (adjacency list) |
|---|---|---|
| BFS | Level-wise traversal; shortest path in unweighted graphs | O(V + E) |
| DFS | Depth-wise traversal; cycle detection, topological sort | O(V + E) |
| Dijkstra | Shortest paths, non-negative weights | O((V + E) log V) with a binary heap |
| Bellman–Ford | Shortest paths, handles negative edges | O(V·E) |
| Floyd–Warshall | All-pairs shortest paths | O(V³) |
| Prim / Kruskal | Minimum spanning tree | O(E log V) |
P, NP and NP-complete (intuition)
- P: problems solvable in polynomial time.
- NP: problems whose solutions can be verified in polynomial time.
- NP-complete: the hardest problems in NP (e.g. SAT, 3-colouring, vertex cover). Whether P = NP is still an open question.
Quick revision
- Binary search needs sorted data and runs in O(log n).
- Merge sort is always O(n log n) but needs O(n) extra space.
- Quick sort’s worst case is O(n²) (bad pivots).
- DP = recursion + remembering answers.