PadhaikoAll subjects

Introduction to Algorithm Analysis

Analysis of Algorithms (ENCT 388)

Open in the Padhaiko app

1.1 Algorithm and its properties, RAM model, time and space complexity, detailed analysis of algorithms, Concept of Aggregate Analysis

Definition

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:

  1. Input: Accepts zero or more externally supplied quantities.
  2. Output: Produces at least one quantity bearing a specified relation to the inputs.
  3. Definiteness: Every instruction is clear, precise, and unambiguous.
  4. Finiteness: Terminates after a finite number of steps for every valid input.
  5. 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:

Definition

Time and Space Complexity

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.

Insertion-Style Inner Loop for Detailed Cost AnalysisC
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:

Example 1

1 (6 marks)

  1. Perform a detailed step-count analysis on the sumUpperTriangle function above for general , and compute the exact number of additions () and inner-loop header tests () when .
  2. Using aggregate analysis, compute the exact total number of bit flips when a -bit binary counter initialized to 0000 is 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 < n executes 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 .

Answer:
  1. ; for , the body executes times and the inner header executes times.
  2. 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.

Definition

Big-O, Big-Omega, and Big-Theta Notations

Let and be asymptotically non-negative functions defined on :

  1. Big- (Asymptotic Upper Bound):

Meaning grows no faster than up to a constant factor for sufficiently large .

  1. Big- (Asymptotic Lower Bound):

Meaning grows at least as fast as for all .

  1. Big- (Asymptotic Tight Bound):

Equivalently, and .

Geometrical Interpretations

When and scaled curves are plotted against :

Summary of Asymptotic Notations and Growth Hierarchy
NotationBound TypeInequality ()AnalogyCommon Complexity Order (Slowest Fastest)
Upper bound
Lower bound
Tight bound
Example 2

2 (5 marks)

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 .

Answer:

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 :

AspectBest CaseWorst Case
DefinitionMinimum 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 SignificanceOptimistic lower bound; rarely guarantees real behaviorPrimary design metric: gives an absolute upper guarantee for every input
Definition

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:

  1. Identify the base case input size where recursion stops and note its constant work .
  2. Count the number of recursive subproblems spawned at each call and the size of each subproblem (e.g., or ).
  3. Add the non-recursive work performed in splitting the input and combining subproblem results.
Common Algorithm Paradigms and Their Recurrence Relations
AlgorithmRecurrence RelationSolution
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:

  1. Draw the root with cost and children of cost (or ).
  2. Compute the sum of costs at each depth .
  3. Determine the tree height (depth where subproblem size reaches : ).
  4. 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:

  1. Guess the form of the solution (often guided by a recursion tree or known pattern), e.g. for all .
  2. 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

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 :

  1. Case 1 (Leaf-heavy): If for some constant , then:
  1. Case 2 (Balanced): If for some constant (most commonly ), then:
  1. Case 3 (Root-heavy): If for some constant , and the regularity condition holds for some constant and sufficiently large , then:
Example 3

3 (8 marks)

Solve the following recurrences using the specified methods (take when evaluating exact values at ):

  1. by the recursion tree method and substitution method.
  2. 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 : .)

Answer:
  1. ( with ).
  2. (Master Case 1, ); (Master Case 3, ).

Exercises

Exercises — Introduction to Algorithm Analysis

Question 1

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).

Answer:

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 .

Question 2

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).

  1. Compute the exact total number of primitive stack operations (where each single push or single pop counts as ).
  2. 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 PUSH operations: primitive pushes (stack size ).
  • MULTIPOP(S, 5) (1 operation): pops items (stack size ).
  • Next PUSH operations: 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 .

Answer:

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.

Question 3

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 .

Answer:

with witnesses , meaning the curve lies strictly between and for all .

Question 4

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 .

Answer:
  1. ().
  2. ().
  3. .
Question 5

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 .

Answer:

(proved for all with ), and .

Iterative and Numeric Algorithms →