Comprehensive Notes on Different Types of
Algorithms
1. Introduction
Algorithms can be classified based on different characteristics. These classifications help in understanding
their properties and choosing appropriate analysis techniques. The major categories of algorithms include:
• Deterministic vs. Randomized
• Offline vs. Online
• Exact vs. Approximate vs. Heuristic vs. Operational
• Categorization based on problem-solving techniques
• Algorithm analysis methods
2. Deterministic vs. Randomized Algorithms
Deterministic Algorithms
• Produce the same output for a given input, following a fixed sequence of steps.
• Example: Binary Search
• Given a sorted array, it repeatedly divides the search interval in half until the element is found or the
interval is empty.
• Time Complexity: O(log n)
Randomized Algorithms
• Use random choices during execution, leading to different outputs or execution paths on the same
input.
• Types:
• Las Vegas Algorithms: Always produce correct results, but runtime varies.
• Monte Carlo Algorithms: May produce incorrect results but guarantee correctness with a certain
probability.
• Example: Randomized QuickSort
• Selects a pivot randomly instead of a fixed position.
• Reduces the likelihood of worst-case O(n^2) complexity.
• Expected Time Complexity: O(n log n)
1
3. Offline vs. Online Algorithms
Offline Algorithms
• Have access to the entire input at the start.
• Example: Sorting Algorithms (Merge Sort, QuickSort)
Online Algorithms
• Process input as it arrives, without prior knowledge of future data.
• Evaluated using competitiveness analysis, comparing performance to an optimal offline algorithm.
• Example: The Ski Rental Problem
• Renting cost = 1 unit/day, Buying cost = B units.
• The skier must decide whether to rent or buy without knowing the total number of skiing days.
• Competitive ratio determines the worst-case cost.
4. Exact vs. Approximate vs. Heuristic vs. Operational Algorithms
Exact Algorithms
• Guarantee an optimal solution.
• Example: Dijkstra's Algorithm (Shortest Path in Graphs)
• Finds the shortest path from a source node to all others.
• Time Complexity: O(V log V + E)
Approximation Algorithms
• Guarantee solutions within a certain factor of the optimal.
• Example: Travelling Salesman Problem (TSP) Approximation
• Uses a Minimum Spanning Tree (MST) for a 2-approximation.
• Time Complexity: O(n^2)
Heuristic Algorithms
• Do not guarantee an optimal solution but find near-optimal ones quickly.
• Example: Genetic Algorithms (Used in AI and Optimization problems)
Operational Algorithms
• Execute a series of predefined computational steps.
• Example: ClustalW (Bioinformatics tool for sequence alignment)
2
5. Categorization Based on Problem-Solving Techniques
1. Recursive Algorithms
• Solves base cases directly, then recurses on subproblems.
• Example: Factorial Calculation
• factorial(n) = n * factorial(n-1)
• Time Complexity: O(n)
2. Backtracking Algorithms
• Explores all solutions using a depth-first recursive search.
• Example: N-Queens Problem
• Places N queens on an NxN chessboard such that no two queens attack each other.
3. Divide-and-Conquer Algorithms
• Divides the problem into subproblems, solves them recursively, and combines results.
• Example: Merge Sort
• Time Complexity: O(n log n)
4. Dynamic Programming (DP)
• Stores results of overlapping subproblems to avoid redundant computation.
• Example: Fibonacci Sequence with DP
• F(n) = F(n-1) + F(n-2)
• Memoization reduces time complexity to O(n).
5. Greedy Algorithms
• Makes locally optimal choices at each step, aiming for a global optimum.
• Works well for optimization problems where local decisions lead to an optimal global solution.
• Example: Huffman Coding (Data Compression)
• Constructs an optimal prefix code for data compression.
• Time Complexity: O(n log n)
• Example: Activity Selection Problem
• Given N activities with start and end times, select the maximum number of non-overlapping
activities.
• Greedy approach: Sort by end time and always pick the next activity that finishes earliest.
• Time Complexity: O(n log n)
• Example: Fractional Knapsack Problem
• Given weights and values of items, maximize total value within a weight limit.
• Greedy approach: Take the most valuable items per weight first.
• Time Complexity: O(n log n)
6. Branch-and-Bound Algorithms
• Used for optimization problems by constructing a tree of subproblems.
• Example: TSP Using Branch-and-Bound
3
7. Brute Force Algorithms
• Tries all possible solutions.
• Example: Checking All Subsets of a Set
• Time Complexity: O(2^n)
6. Algorithm Analysis
Common Time Complexity Notations
• O(f(n)): Upper bound.
• Ω(f(n)): Lower bound.
• Θ(f(n)): Tight bound.
Run-Time Analysis Methods
1. Worst Case: Maximum runtime for any input.
2. Best Case: Minimum runtime.
3. Average Case: Expected runtime over all inputs.
4. Expected Run-Time: For randomized algorithms.
5. Amortized Analysis: Averages cost over multiple operations.
6. Competitiveness Analysis: Used for online algorithms.
7. Example: Randomized QuickSort Analysis
• Deterministic QuickSort Worst Case: O(n²)
• Randomized QuickSort Expected Case: O(n log n)
8. Amortized Analysis
Used when worst-case analysis overestimates real cost.
Techniques for Amortized Analysis
1. Aggregate Method
2. Computes the total cost and averages over n operations.
3. Example: Stack operations (Push, Pop, MultiPop) → O(1) per operation.
4. Accounting Method
5. Assigns artificial costs to operations.
4
6. Example: Push costs 2 units, Pop and MultiPop cost 0.
7. Potential Method
8. Uses a "potential energy" function to balance cost.
9. Example: Stack potential = number of elements.
Conclusion
• Different classifications provide insight into algorithm behavior.
• Choosing the right analysis method is crucial for understanding efficiency.
• Understanding trade-offs helps in algorithm selection for specific applications.
Would you like more examples or explanations on any section?