Analysis of Algorithms
Why Analyze Algorithms?
Algorithm analysis helps us predict the performance of an algorithm before implementing it. It answers: How does the algorithm scale as input grows? Two algorithms that both solve the same problem correctly can differ by orders of magnitude in performance.
Types of Analysis
Type Description Notation
Worst Case Maximum time for any input of size n. Most commonly used. Big-O: O(f(n)) Best Case Minimum time for the most favorable input. Big-Omega: Ω(f(n)) Average Case Expected time over all possible inputs (requires probability). Big-Theta: Θ(f(n)) Amortized Average cost per operation over a sequence of operations. Amortized O(f(n))
Priori vs Posteriori Analysis
Priori Analysis Posteriori Analysis
Theoretical — done before implementation Empirical — done after implementation by running the program Language and hardware independent Depends on hardware, OS, compiler Uses mathematical models (Big-O) Uses actual timing measurements Preferred in DAA Used for benchmarking and profiling
Counting Operations — Step Count Method
public class StepCount {
/*
* Analyze: sum of array elements
*
* Line 1: int total = 0; → 1 step
* Line 2: for (int i = 0; ...) → n+1 steps (condition checked n+1 times)
* Line 3: total += arr[i]; → n steps (body runs n times)
* Line 4: return total; → 1 step
*
* Total steps = 1 + (n+1) + n + 1 = 2n + 3
* Drop constants and lower terms → O(n)
*/
static int sum(int[] arr) {
int total = 0; // 1 step
for (int i = 0; i < arr.length; i++) { // n+1 steps
total += arr[i]; // n steps
}
return total; // 1 step
}
/*
* Analyze: bubble sort
*
* Outer loop: n-1 iterations
* Inner loop: n-1, n-2, ..., 1 iterations
* Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2
* → O(n²)
*/
static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) { // n-1 times
for (int j = 0; j < n - i - 1; j++) { // n-i-1 times
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/*
* Analyze: binary search
*
* Each iteration: search space halves
* After k iterations: n / 2^k = 1 → k = log₂(n)
* → O(log n)
*/
static int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) { // logâ‚‚(n) iterations
int mid = (lo + hi) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
}
Simplification Rules
Drop constant factors: O(3n) → O(n)
Drop lower-order terms: O(n² + n) → O(n²)
Sequential blocks: O(n) + O(n²) → O(n²) (dominant term)
Nested loops multiply: O(n) × O(n) = O(n²)
Logarithm base doesn't matter: O(logâ‚‚ n) = O(log n)