Introduction to Algorithm Analysis
Open in the Padhaiko app1.1 Algorithm and its properties, RAM model, time and space complexity, detailed analysis of algorithms, Concept of Aggregate Analysis
Algorithm and Its Five Properties
An algorithm is a finite, unambiguous, step-by-step computational procedure that transforms a set of valid inputs into desired outputs. Every valid algorithm must satisfy five properties:
- Input: Accepts zero or more externally supplied quantities.
- Output: Produces at least one quantity bearing a specified relation to the inputs.
- Definiteness: Every instruction is clear, precise, and unambiguous.
- Finiteness: Terminates after a finite number of steps for every valid input.
- Effectiveness: Every operation is basic enough to be carried out exactly in finite time using paper and pencil.
The RAM (Random Access Machine) Model
To analyze algorithms independently of hardware, compiler optimizations, or programming languages, we use the Random Access Machine (RAM) model:
- Instructions execute sequentially one after another (no concurrent operations).
- Each primitive operation—arithmetic (
+,-,*,/), data movement (assignment, array indexing), control flow (branch, loop test, return), and logical comparison—takes constant time ( unit of time). - Memory consists of an unbounded sequence of registers/words, each accessible in time, and each integer or floating-point value fits in a single word.
Time and Space Complexity
- Time Complexity : The total number of primitive operations executed by an algorithm as a function of the input size .
- Space Complexity : The total memory required by an algorithm as a function of , split into:
where is the fixed part (code space, simple scalar variables, constants independent of ) and is the variable/auxiliary part (dynamically allocated structures, input-dependent arrays, and recursion call stack frames).
Detailed Analysis of Algorithms
In detailed (step-count) analysis, each line of code is assigned its per-execution cost and its execution frequency as a function of , and the total cost is summed explicitly.
int sumUpperTriangle(int A[][10], int n) {
int s = 0; // c1, executed 1 time
for (int i = 0; i < n; i++) { // c2, executed n + 1 times
for (int j = i; j < n; j++) { // c3, executed sum_{i=0}^{n-1} (n - i + 1) times
s = s + A[i][j]; // c4, executed sum_{i=0}^{n-1} (n - i) times
}
}
return s; // c5, executed 1 time
}Concept of Aggregate Analysis
Aggregate analysis is the simplest method of amortized analysis. Instead of bounding each operation individually by its worst-case cost (which can be overly pessimistic), we determine an upper bound on the total cost of a sequence of operations, and then define the amortized cost per operation as:
1
- Perform a detailed step-count analysis on the
sumUpperTrianglefunction above for general , and compute the exact number of additions () and inner-loop header tests () when . - Using aggregate analysis, compute the exact total number of bit flips when a -bit binary counter initialized to
0000is incremented times, and find the average (amortized) flips per increment.
Detailed step count for sumUpperTriangle:
- Line
int s = 0;executes time;return s;executes time. - Outer loop test
i < nexecutes times (). - For a fixed , inner loop runs for ( body executions and header tests):
Total running time is:
Substituting : executes times and executes times.
Aggregate bit flips for increments of a -bit counter: Count how many times each bit position flips over increments (0000 1000):
- Bit flips on every increment: flips.
- Bit flips every nd increment: flips.
- Bit flips every th increment: flips.
- Bit flips every th increment: flip.
Total flips , and amortized cost per increment is .
- ; for , the body executes times and the inner header executes times.
- Total bit flips for increments ; amortized flips per operation ().
1.2 Asymptotic notations (Big-, Big-, and Big-), their geometrical interpretations and examples
Asymptotic notations describe the limiting behavior of a positive function (typically running time or space) as the input size , ignoring constant factors and lower-order terms.
Big-O, Big-Omega, and Big-Theta Notations
Let and be asymptotically non-negative functions defined on :
- Big- (Asymptotic Upper Bound):
Meaning grows no faster than up to a constant factor for sufficiently large .
- Big- (Asymptotic Lower Bound):
Meaning grows at least as fast as for all .
- Big- (Asymptotic Tight Bound):
Equivalently, and .
Geometrical Interpretations
When and scaled curves are plotted against :
- For : Beyond the vertical threshold , the curve always lies on or below the upper-envelope curve (crossing may occur for ).
- For : Beyond , the curve always lies on or above the lower-envelope curve .
- For : Beyond , is sandwiched between (below) and (above).
| Notation | Bound Type | Inequality () | Analogy | Common Complexity Order (Slowest Fastest) |
|---|---|---|---|---|
| Upper bound | ||||
| Lower bound | ||||
| Tight bound |
2
Prove using the formal definitions that satisfies , and find the smallest integer when is chosen for the upper bound .
Proving and : For all , we have and , so:
Also, since for all :
Thus for all , proving .
Finding when : We require:
The positive root of is . Testing consecutive integers:
- At : (fails).
- At : (holds for all ).
Thus the smallest valid integer threshold is .
With , for all , so . For , the smallest valid threshold is .
1.3 Concept of best case, average case and worst case performance of an algorithm
Because an algorithm's running time often depends on the arrangement or values of the input (not just its size ), we distinguish three performance measures for inputs of size :
| Aspect | Best Case | Worst Case |
|---|---|---|
| Definition | Minimum running time over all inputs of size | Maximum running time over all inputs of size |
| Example (Linear Search) | Target is at index : comparison, | Target is at last index or absent: comparisons, |
| Example (Insertion Sort) | Input already sorted: inner loop exits immediately, | Input reverse-sorted: shifts, |
| Practical Significance | Optimistic lower bound; rarely guarantees real behavior | Primary design metric: gives an absolute upper guarantee for every input |
Average Case Performance
Average Case Complexity is the expected running time over a specified probability distribution of all valid inputs of size :
where is the set of inputs of size and is the probability of input . For example, in linear search for a key present with probability (and equally likely at any of the positions):
When , .
1.4 Modeling algorithms by recurrence relation
A recurrence relation defines a function recursively in terms of its values on smaller inputs, together with one or more base cases for small (typically ).
To model a recursive algorithm by a recurrence:
- Identify the base case input size where recursion stops and note its constant work .
- Count the number of recursive subproblems spawned at each call and the size of each subproblem (e.g., or ).
- Add the non-recursive work performed in splitting the input and combining subproblem results.
| Algorithm | Recurrence Relation | Solution |
|---|---|---|
| Binary Search | ||
| Recursive Linear Search / Factorial | ||
| Merge Sort | ||
| Strassen's Matrix Multiplication | ||
| Tower of Hanoi / Recursive Fibonacci |
1.5 Solving recurrence relation for evaluating computational complexity
1.5.1 Recursion tree method
In the recursion tree method, we expand the recurrence into a tree where each node stores the non-recursive cost at that recursive call:
- Draw the root with cost and children of cost (or ).
- Compute the sum of costs at each depth .
- Determine the tree height (depth where subproblem size reaches : ).
- Sum all level costs plus the leaf cost ().
1.5.2 Substitution method
The substitution method (mathematical induction) proves an asymptotic bound in two steps:
- Guess the form of the solution (often guided by a recursion tree or known pattern), e.g. for all .
- Prove by strong induction: assume the bound holds for all positive integers (in particular or ), substitute into the recurrence, and algebraically show that holds for as well (if a lower-order term blocks the proof, subtract a lower-order term from the inductive hypothesis, e.g. ).
1.5.3 Using masters theorem
Master Theorem (Standard Form)
Let and be constants, let be an asymptotically positive function, and let be defined on the non-negative integers by:
where means either or . Compare against the watershed function :
- Case 1 (Leaf-heavy): If for some constant , then:
- Case 2 (Balanced): If for some constant (most commonly ), then:
- Case 3 (Root-heavy): If for some constant , and the regularity condition holds for some constant and sufficiently large , then:
3
Solve the following recurrences using the specified methods (take when evaluating exact values at ):
- by the recursion tree method and substitution method.
- and using the Master Theorem.
Part 1 — Recursion tree and substitution for :
- Recursion Tree: Root (level ) has cost . Level has nodes of cost (sum ). Level has nodes each of cost , giving level sum .
- Tree height is , leaving leaves each of cost :
For , .
- Substitution Verification (): Assume for . Then:
which holds for all .
Part 2 — Applying the Master Theorem:
- For : . Since (), Case 1 gives . (Exact at : .)
- For : . Since () and regularity holds:
Case 3 gives . (Exact at : .)
- ( with ).
- (Master Case 1, ); (Master Case 3, ).
Exercises
Exercises — Introduction to Algorithm Analysis
Define an algorithm and list its five essential properties. Explain the assumptions of the RAM (Random Access Machine) model and distinguish between fixed and variable parts of space complexity.
Algorithm and its five properties: An algorithm is a finite sequence of well-defined computational steps that takes input and produces output. Its five properties are Input ( inputs), Output ( output), Definiteness (unambiguous instructions), Finiteness (terminates in finite steps), and Effectiveness (each step is basic and executable in finite time).
RAM model and space complexity: In the RAM model, instructions execute sequentially (one at a time), memory words take time to access, and every primitive arithmetic, assignment, or comparison operation costs unit of time. Total space splits into the fixed part (instruction code, constants, simple scalar variables) and the variable part (instance-dependent dynamic data structures and recursion stack space).
An algorithm satisfies Input, Output, Definiteness, Finiteness, and Effectiveness. The RAM model assumes sequential execution with unit-time primitive operations and word memory access. Space complexity separates fixed scalar/code space from input-dependent dynamic/stack space .
Consider a stack initially empty on which we perform a sequence of operations: consecutive PUSH operations, followed by MULTIPOP(S, 5), then consecutive PUSH operations, and finally MULTIPOP(S, 3).
- Compute the exact total number of primitive stack operations (where each single push or single pop counts as ).
- Explain via aggregate analysis why the amortized cost per operation over any operations is , and compute the exact amortized cost for the -operation sequence above.
Counting exact operations in the -operation sequence:
- First
PUSHoperations: primitive pushes (stack size ). MULTIPOP(S, 5)(1 operation): pops items (stack size ).- Next
PUSHoperations: primitive pushes (stack size ). MULTIPOP(S, 3)(1 operation): pops items (stack size ).
Total operations in sequence . Total primitive pushes , total primitive pops , so total primitive cost .
Aggregate analysis bound and exact amortized cost: Every element can be popped at most once for each time it is pushed. If PUSH operations occur in a sequence of operations, at most pops occur in total across all POP and MULTIPOP calls, so and . For our -operation sequence, the exact amortized cost per operation is .
Total primitive stack actions over operations, giving an exact amortized cost of per operation. By aggregate analysis, any sequence of stack operations costs at most , yielding amortized cost per operation.
Prove formally using the definitions of , , and that is , clearly stating valid positive constants , and . Also interpret the result geometrically.
Upper bound (): For all , dropping the negative term and bounding :
So holds with and .
Lower bound () and tightness (): For all , and , so:
Thus holds for all with and , proving . Geometrically, for all , the graph of remains sandwiched between the curves and .
with witnesses , meaning the curve lies strictly between and for all .
Solve the following recurrence relations using the Master Theorem (and check for exact values at and respectively):
Solving (1) : Here . Since , Master Theorem Case 2 () yields . At : .
Solving (2) : Here . Since , Master Theorem Case 2 yields . At : , , .
Solving (3) : Here . Since (), Master Theorem Case 1 yields .
- ().
- ().
- .
Use the recursion tree method to guess a bound for with , and then prove using the substitution method. Also evaluate .
Guessing via recursion tree: The tree is a single chain of depth with node costs and leaf :
At , .
Proving by substitution (induction): Assume for all . For and :
For and , , so . Base case: . Hence .
(proved for all with ), and .