ALGORITHM ANALYSIS
Lesson Overview
Every computer program is built upon an algorithm a series of clearly defined steps used to solve a
problem. However, not all algorithms are equally efficient. Some run faster, while others consume
less memory. Algorithm analysis allows us to measure these differences scientifically. It focuses on
how much time and memory an algorithm uses, helping programmers choose or design better
solutions. In real-world systems such as databases, online searches, or AI training, efficiency
determines how practical an algorithm is. This lesson introduces the foundation of algorithm
analysis, emphasizing time and space complexity, different performance cases, and standard growth
classes expressed in Big-O notation.
Lesson Objectives
At the end of this lesson, students should be able to:
1. Define algorithm analysis and explain its importance.
2. Identify and describe the two parameters used in algorithm evaluation: time and space.
3. Differentiate between best-case, average-case, and worst-case time complexities.
4. Classify algorithms according to standard complexity classes such as O(1), O(log n), O(n),
and O(n²).
5. Analyze simple iterative programs and apply Big-O notation to determine their efficiency.
6. Apply the concepts learned to real examples such as Linear Search and Binary Search.
Definition and Purpose of Algorithm Analysis
Algorithm analysis is the process of determining how efficiently an algorithm performs in terms of
time and memory usage. Instead of measuring real execution time—which depends on processor
speed, language, or compiler—we count the number of basic operations an algorithm performs as
the input size n grows. The result is expressed as a mathematical function, T(n) for time or S(n) for
space. This method provides a fair, hardware-independent way to compare algorithms. For example,
two programs can sort the same list, but one might finish in a few seconds while another takes
minutes. Analyzing them mathematically tells us which algorithm scales better as input grows.
Parameters of Algorithm Analysis
1. Time Complexity
Time complexity measures the total number of basic operations an algorithm performs as a function
of the input size n. It ignores external factors such as CPU speed or system load. The goal is to
understand the rate of growth of the running time, not the exact duration.
If an algorithm’s running time is given by
T(n) = a₀ + a₁n + a₂n² + … + aₖnᵏ,
the term with the highest degree dominates when n becomes large. Lower-order terms and constants
are dropped, leaving only the dominant term.
Example:
T(n) = 3n² + 5n + 2 → O(n²)
That means as n grows, the algorithm’s time increases roughly with the square of n.
Example in C++
for (int i = 0; i < n; i++) {
cout << i;
}
The loop runs n times, each iteration executing one constant-time statement. Therefore, T(n) = n,
and the time complexity is O(n) (linear time).
2. Space Complexity
Space complexity measures how much memory an algorithm uses relative to input size. It includes
the memory required for input storage and the auxiliary space for temporary variables or recursive
calls. Mathematically,
S(n) = Input Space + Auxiliary Space.
Example:
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
Only one extra variable sum is used regardless of n, so space complexity is O(1) (constant).
Efficient algorithms often aim for both low time complexity and low space complexity, but
sometimes a trade-off exists: saving time may require using more memory.
Types of Time Complexity Analysis
Algorithms behave differently depending on input values. We therefore analyze them in three
standard scenarios.
1. Best Case (Ω Notation)
This represents the minimum possible running time—the most favorable condition for the
algorithm.
Example: In Linear Search, if the target is the first element, only one comparison is made.
T(n) = O(1).
2. Average Case (Θ Notation)
This is the expected running time for a typical or random input.
Example: If the target in a list of n elements is equally likely to appear anywhere, the algorithm
performs about n/2 comparisons on average.
T(n) ≈ O(n).
3. Worst Case (O Notation)
This is the maximum time the algorithm will take for any input of size n. It provides a safe upper
bound and is the standard measure used by computer scientists.
Example: If the searched element is the last one or not found at all, Linear Search performs n
comparisons.
T(n) = O(n).
Most analysis focuses on the worst case because it guarantees performance limits.
Illustrative Example: Linear Search
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i;
}
return -1;
}
In the best case, the first element matches the key → 1 comparison → O(1).
In the average case, key is in the middle → n/2 comparisons → O(n).
In the worst case, key not present → n comparisons → O(n).
Hence Linear Search has O(n) time complexity and O(1) space complexity.
Why Worst-Case Analysis Matters
1. It predicts the longest time required for an algorithm to finish.
2. It ensures system reliability under all conditions.
3. It provides a standard basis for comparing different algorithms.
4. It is critical in safety-critical applications where delays are unacceptable (e.g., medical or
aviation systems).
Growth of Algorithms
As input size increases, algorithms grow at different rates. Understanding how performance scales
helps in choosing the right method. When n doubles, the running time of O(1) remains constant,
O(n) doubles, and O(n²) quadruples. This growth pattern shows why a poorly chosen algorithm
becomes impractical for large datasets.
Standard Complexity Classes
Complexity classes group algorithms based on how quickly their running time or memory grows
with input size n.
1. Constant Time — O(1)
Execution time remains the same regardless of input size.
Example:
int x = arr[0];
Accessing an array element takes constant time.
Graphically, this is represented by a flat horizontal line showing no growth as n increases.
2. Logarithmic Time — O(log n)
Each step reduces the problem size by a constant factor, often by half.
Example: Binary Search on a sorted array.
For n = 1024 elements, log₂(1024) = 10 steps.
O(log n) grows very slowly, as shown by a curve that rises quickly at first and then flattens.
3. Linear Time — O(n)
Running time grows directly in proportion to n.
Example:
for (int i = 0; i < n; i++) {
process(arr[i]);
}
If n doubles, time roughly doubles.
Graphically, O(n) is a straight diagonal line.
4. Log-Linear Time — O(n log n)
Occurs in efficient divide-and-conquer algorithms such as Merge Sort and QuickSort. Each division
contributes a log n factor, and processing all elements adds n.
This is the most efficient complexity for general sorting algorithms.
5. Quadratic Time — O(n²)
Typical of algorithms with nested loops.
Example:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cout << i + j;
Total operations = n × n = n².
On a graph, the curve for O(n²) rises steeply; doubling n multiplies the time by four.
6. Exponential Time — O(2ⁿ)
Each additional input doubles the processing time.
Example: Recursive Fibonacci implementation.
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
Even small increases in n make runtime explode. This complexity is typical of brute-force recursive
solutions.
7. Factorial Time — O(n!)
Found in algorithms that generate all permutations or combinations, such as the Traveling Salesman
Problem. It becomes impractical for anything beyond very small n.
Comparison Table of Growth Rates
Complexity Type Typical Example Relative Speed
O(1) Constant Array element access Fastest
O(log n) Logarithmic Binary Search Very fast
O(n) Linear Linear Search Moderate
O(n log n) Log-Linear Merge Sort Efficient
O(n²) Quadratic Bubble Sort Slow
O(2ⁿ) Exponential Recursive Fibonacci Very slow
O(n!) Factorial Traveling Salesman Extremely slow
When drawn on a graph with time on the y-axis and input size on the x-axis, the curves clearly
show O(1) as flat, O(log n) rising gently, O(n) diagonal, O(n²) curving steeply, and O(2ⁿ)/O(n!)
shooting almost vertically.
Analyzing Loops
Loop structure is a practical way to estimate complexity.
Example 1: Single Loop
for (int i = 0; i < n; i++) {
cout << i;
}
Executes n times → O(n).
Example 2: Nested Loop
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << i + j;
}
}
Outer loop n times × inner loop n times = n² → O(n²).
Example 3: Constant Inner Work
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
cout << i + j;
}
}
Inner loop fixed (10) → n × 10 = O(n).
Example 4: Doubling Step
int i = 1;
while (i <= n) {
i *= 2;
}
i doubles each time → number of iterations ≈ log₂ n → O(log n).
Example 5: Triangular Loop
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
cout << i + j;
}
}
Total iterations = 1 + 2 + 3 + … + (n – 1) = n(n – 1)/2 ≈ O(n²).
Case Study: Binary Search
Binary Search works on sorted arrays by repeatedly halving the search range.
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
Each iteration cuts the problem in half, giving a logarithmic time complexity.
If n = 1,000,000, log₂ n ≈ 20 steps only.
This efficiency explains why Binary Search is preferred over Linear Search for sorted data.
Algorithm Requires Sorting? Steps for n = 1000 Time Complexity
Linear Search No 1000 O(n)
Binary Search Yes ~10 O(log n)
Practical Importance of Algorithm Analysis
1. Scalability Prediction: Knowing how runtime grows helps anticipate performance issues
before deployment.
2. Optimization: Identifies bottlenecks and directs improvements to the most time-consuming
parts.
3. Resource Management: Balances CPU time and memory usage.
4. Algorithm Selection: Helps choose between alternatives; e.g., Merge Sort (O(n log n)) is
better than Bubble Sort (O(n²)) for large data.
5. Reliability: Ensures consistent performance even with large or worst-case inputs.
Common Mistakes in Complexity Evaluation
Treating constants as significant; O(2n) simplifies to O(n).
Confusing best-case with worst-case analysis.
Ignoring nested loops and their multiplicative effects.
Misinterpreting Big-O as exact running time instead of a growth rate.
Forgetting that input/output operations are usually not counted in algorithmic complexity.
Practice Exercises
1. Determine the time complexity of
for (int i = 0; i < n; i++)
for (int j = 0; j < 10; j++)
cout << i + j;
Answer: Inner loop constant → O(n).
2. Analyze
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
cout << "*";
3. Explain why Binary Search is faster than Linear Search when the array is sorted.
Answer: Binary Search halves the search space each step → O(log n), while Linear Search
checks every element → O(n).
Lesson Summary
Algorithm analysis provides a framework for evaluating efficiency in terms of time and memory.
Key takeaways:
Two parameters: Time Complexity (T(n)) and Space Complexity (S(n)).
Three analysis types: Best, Average, and Worst Case.
Big-O Notation describes the upper bound or worst-case growth.
Common classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), and O(n!).
Efficient algorithms handle large inputs gracefully; inefficient ones quickly become
unusable.
In practical terms, always prefer algorithms with lower order growth, especially for large-
scale data problems.
Greedy Algorithms
Lesson Overview
The Greedy Algorithm paradigm is a fundamental problem-solving approach used in algorithm
design. It works by building a solution step by step, always making the choice that seems best at the
moment the “greedy” choice. This approach often provides efficient and simple algorithms for
solving optimization problems, particularly when a problem exhibits specific properties such as the
greedy-choice property and optimal substructure.
In this lesson, we explore the concept of the greedy method, understand its principles, and apply it
to two classic problems: the Activity Selection Problem and Huffman Coding for data compression.
Lesson Objectives
By the end of this lesson, students should be able to:
1. Define the Greedy Algorithm paradigm and its core principles.
2. Explain the concept of locally optimal choices leading to a globally optimal solution.
3. Identify when a problem satisfies the greedy-choice property and optimal substructure.
4. Apply the greedy strategy to solve optimization problems such as Activity Selection and
Huffman Coding.
5. Analyze the time complexity of greedy algorithms.
1. Core Concept: The Greedy Algorithm Paradigm
A Greedy Algorithm builds up a solution step by step, choosing the most beneficial option available
at each stage. Once a decision is made, it is never reconsidered. The idea is to make the locally
optimal choice with the hope that this leads to a globally optimal solution.
Core Principle
“At each stage, choose the option that looks best in the current situation.”
The greedy method doesn’t look ahead to see if the current decision will yield the overall best
solution it trusts that local optimization will lead to a global one.
When to Use Greedy Algorithms
The greedy method works best for problems that exhibit:
1. Greedy-choice property – A globally optimal solution can be arrived at by choosing local
optima.
2. Optimal substructure – An optimal solution to the problem contains optimal solutions to its
subproblems.
Common Examples
Prim’s Algorithm – finds the Minimum Spanning Tree (MST) by always adding the smallest
weight edge connecting a vertex to the tree.
Kruskal’s Algorithm – builds an MST by always adding the smallest edge that doesn’t form
a cycle.
Dijkstra’s Algorithm – finds the shortest paths from a source node to all others by always
expanding the closest unvisited node.
Huffman Coding – compresses data by assigning shorter codes to more frequent symbols.
Activity Selection – selects the maximum number of non-overlapping activities.
Advantages and Disadvantages of Greedy Algorithms
Advantages Disadvantages
May fail to produce the globally optimal solution
Simple and easy to implement.
in some problems.
Works efficiently when greedy-choice property Requires proof of correctness for each new
and optimal substructure hold. problem.
Not suitable for problems requiring exhaustive
Often leads to fast, practical algorithms.
exploration (e.g., backtracking).
2. Activity Selection Problem
The Activity Selection Problem is a classic example that demonstrates how the greedy approach can
be used effectively for optimization.
Problem Definition
Given n activities, each with a start time s[i] and finish time f[i], select the maximum number
of activities that do not overlap, assuming a single person can perform only one activity at a time.
Objective
Maximize the number of non-overlapping activities.
Greedy Choice
Select the activity that finishes earliest, as this leaves the maximum remaining time for other
activities.
Algorithm Steps
1. Sort all activities in ascending order by their finish times.
2. Select the first activity (the one that finishes earliest).
3. Iterate through the remaining activities:
If the start time of the current activity ≥ finish time of the last selected activity, select
it.
C++ Implementation
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity {
int start, finish;
};
bool compare(Activity a, Activity b) {
return [Link] < [Link];
}
void activitySelection(Activity arr[], int n) {
sort(arr, arr + n, compare);
cout << "Selected activities: " << endl;
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << ")";
for (int j = 1; j < n; j++) {
if (arr[j].start >= arr[i].finish) {
cout << ", (" << arr[j].start << ", " << arr[j].finish << ")";
i = j;
}
}
}
Example Input
Activity Start Time Finish Time
A₁ 1 3
A₂ 2 5
A₃ 4 6
A₄ 6 8
A₅ 5 7
A₆ 8 9
Step-by-Step Execution
1. Sort activities by finish time: (1,3), (2,5), (4,6), (5,7), (6,8), (8,9)
2. Select the first activity: (1,3).
3. Next, pick (4,6) since it starts after 3.
4. Then select (6,8) since it starts after 6.
5. Finally, select (8,9).
✅ Selected Activities: (1,3), (4,6), (6,8), (8,9)
✅ Maximum Activities = 4
Complexity Analysis
Sorting: O(n log n)
Selection Loop: O(n)
Overall Time Complexity: O(n log n)
Greedy Property Verification
Greedy-choice property: Choosing the earliest finishing activity never prevents finding an
optimal solution.
Optimal substructure: Once one activity is chosen, the remaining problem is the same with
reduced activity set.
3. Huffman Coding
Huffman Coding is a greedy algorithm used for lossless data compression.
It assigns variable-length codes to input characters, shorter codes for more frequent characters, and
longer codes for less frequent ones.
Objective
Minimize the total number of bits required to encode a message.
Key Idea
Combine the two least frequent symbols repeatedly to form a binary tree (called a Huffman Tree).
The frequencies determine the tree structure, and codes are assigned according to the path:
Left edge → 0
Right edge → 1
Algorithm Steps
1. Create a leaf node for each character and its frequency.
2. Insert all nodes into a min-priority queue (sorted by frequency).
3. While there is more than one node in the queue:
Remove the two nodes with the smallest frequencies.
Create a new internal node with frequency = sum of the two nodes.
Add this new node back to the queue.
4. The remaining node is the root of the Huffman Tree.
5. Assign codes by traversing the tree.
Example
Character Frequency
A 5
B 9
C 12
D 13
E 16
F 45
Step 1: Build a min-heap based on frequencies.
Step 2: Combine smallest frequencies repeatedly:
Step Combined Nodes New Frequency
1 A(5) + B(9) 14
2 C(12) + D(13) 25
3 14 + E(16) 30
4 25 + 30 55
5 45 + 55 100
From the final tree, assign codes:
Character Huffman Code
F 0
C 100
D 101
A 1100
B 1101
E 111
Encoded message length is minimized, as frequent characters like F use fewer bits.
C++ Implementation (Simplified)
#include <iostream>
#include <queue>
using namespace std;
struct Node {
char data;
int freq;
Node *left, *right;
Node(char d, int f) : data(d), freq(f), left(NULL), right(NULL) {}
};
struct Compare {
bool operator()(Node* l, Node* r) {
return l->freq > r->freq;
}
};
void printCodes(Node* root, string str) {
if (!root) return;
if (root->data != '$')
cout << root->data << ": " << str << endl;
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
4. Characteristics of the Greedy Approach
Property Explanation
A global optimum can be reached by choosing a local optimum at each
Greedy-choice property
stage.
Optimal substructure A problem can be broken into smaller subproblems that are also optimal.
Irrevocability Once a choice is made, it cannot be changed later.
When both properties are satisfied, the greedy algorithm provides an optimal solution.
5. Common Examples of Greedy Algorithms
1. Coin Change Problem (for specific denominations)
2. Fractional Knapsack Problem (partial items allowed)
3. Minimum Spanning Tree (Prim’s and Kruskal’s)
4. Shortest Path Problem (Dijkstra’s Algorithm)
5. Job Sequencing Problem
Each example involves selecting the “best-looking” option at each step — for instance, the shortest
edge in a graph, or the item with the highest value-to-weight ratio.
6. Comparison: Greedy vs. Dynamic Programming
Aspect Greedy Algorithm Dynamic Programming
Choice Basis Local best choice Global optimal combination
Structure Top-down, immediate decisions Bottom-up, overlapping subproblems
Memory Use Less (no table) More (stores results)
Examples Dijkstra’s, Kruskal’s Floyd-Warshall, Bellman-Ford
7. Assignment
Assignment:
1. Solve the Activity Selection problem using the greedy strategy.
2. Write a short report explaining why Huffman coding satisfies the greedy-choice property.
Lesson Summary
The Greedy Algorithm paradigm is an intuitive method that constructs solutions by making the most
immediate beneficial choice at each step. It is fast and elegant but requires the problem to exhibit
both the greedy-choice property and optimal substructure to ensure correctness. The Activity
Selection Problem demonstrates how greedy methods can achieve globally optimal results, while
Huffman Coding shows how data compression can be achieved by repeatedly combining minimal
frequencies. Greedy algorithms play an essential role in optimization, networking, compression, and
graph theory, forming a vital foundation in algorithm design.