Algorithm Concepts – Detailed Notes
Algorithm Analysis & Efficient Algorithms
An algorithm is a step-by-step procedure used to solve a problem efficiently.
Main characteristics:
• Input and output
• Finite number of steps
• Clearly defined instructions
• Effective operations
Algorithm analysis measures:
• Time Complexity – execution time
• Space Complexity – memory usage
Cases:
• Best Case
• Worst Case
• Average Case
Asymptotic Notations
Asymptotic analysis studies performance for large input sizes.
Important notations:
• Big O – Upper bound / worst case
• Omega – Lower bound / best case
• Theta – Exact bound
Common complexities:
O(1), O(log n), O(n), O(n log n), O(n²), O(2■)
Divide and Conquer
This technique divides a problem into smaller subproblems, solves them recursively, and combines results.
Steps:
1. Divide
2. Conquer
3. Combine
Examples:
• Merge Sort
• Quick Sort
• Binary Search
Dynamic Programming
Dynamic Programming solves overlapping subproblems efficiently by storing previous results.
Methods:
• Memoization
• Tabulation
Example:
Fibonacci sequence:
F(n) = F(n−1) + F(n−2)
DP reduces time complexity significantly.
Greedy Algorithms
Greedy algorithms choose the best local solution at every step.
Properties:
• Greedy Choice Property
• Optimal Substructure
Examples:
• Kruskal’s Algorithm
• Prim’s Algorithm
• Dijkstra’s Algorithm
Sorting Algorithms
Merge Sort:
• Divide and Conquer
• Complexity: O(n log n)
Heap Sort:
• Uses Binary Heap
• Complexity: O(n log n)
Quick Sort:
• Uses pivot partitioning
• Average Complexity: O(n log n)
• Worst Complexity: O(n²)
Linear Time Sorting:
• Counting Sort
• Radix Sort
• Bucket Sort
Medians and Order Statistics
Order statistics deal with finding kth smallest or largest elements.
Examples:
• Minimum = 1st order statistic
• Maximum = nth order statistic
• Median = middle value
Hash Tables
Hash tables store key-value pairs.
Hash Function:
h(k) = k mod m
Collision Handling:
• Chaining
• Open Addressing
Applications:
• Databases
• Dictionaries
• Searching
Binary Search Trees (BST)
BST properties:
• Left subtree < root
• Right subtree > root
Operations:
• Insert
• Delete
• Search
Average complexity: O(log n)
Worst case: O(n)
Red-Black Trees
A self-balancing Binary Search Tree.
Rules:
• Every node is red or black
• Root is black
• No two adjacent red nodes
• Same black height on paths
Complexity: O(log n)
Disjoint Sets
Used for grouping elements.
Operations:
• Make Set
• Union
• Find
Applications:
• Kruskal’s Algorithm
• Network Connectivity
Graph Representation
Graphs contain:
• Vertices (nodes)
• Edges (connections)
Representations:
• Adjacency Matrix
• Adjacency List
Breadth First Search (BFS)
BFS traverses graph level by level using a Queue.
Applications:
• Shortest path in unweighted graph
• Network broadcasting
Complexity: O(V + E)
Depth First Search (DFS)
DFS explores deeply before backtracking.
Uses recursion or stack.
Applications:
• Cycle detection
• Topological sorting
• SCC detection
Complexity: O(V + E)
Topological Sort
Used for Directed Acyclic Graphs (DAG).
Applications:
• Task scheduling
• Dependency management
Strongly Connected Components (SCC)
In SCC every node is reachable from every other node.
Algorithms:
• Kosaraju Algorithm
• Tarjan Algorithm
Minimum Spanning Tree (MST)
A spanning tree with minimum total edge weight.
Kruskal’s Algorithm:
• Sort edges
• Add smallest edge avoiding cycles
• Uses Disjoint Sets
Prim’s Algorithm:
• Starts from one vertex
• Adds minimum cost edge repeatedly
Dijkstra’s Algorithm
Finds shortest path from a single source vertex.
Conditions:
• Works for non-negative weights
Complexity: O(E log V)
All Pair Shortest Paths
Find shortest paths between all pairs of vertices.
Floyd-Warshall Algorithm:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
Complexity: O(V³)
Matrix Multiplication
If A is m×n and B is n×p,
then result matrix C is m×p.
Formula:
C[i][j] = Σ A[i][k] × B[k][j]
Important Exam Comparison Table
Algorithm Technique Complexity
Merge Sort Divide & Conquer O(n log n)
Quick Sort Divide & Conquer Average O(n log n)
Heap Sort Heap O(n log n)
BFS Queue O(V+E)
DFS Stack/Recursion O(V+E)
Dijkstra Greedy O(E log V)
Floyd-Warshall Dynamic Programming O(V³)
Kruskal Greedy O(E log E)
Prim Greedy O(E log V)