Unit 1: Introduction

I. Foundations of Algorithm Design and Analysis

Algorithm design develops finite, precise procedures for solving computational problems, while algorithm analysis predicts the resources those procedures require independently of a particular implementation or machine.

• Algorithm: A finite sequence of unambiguous steps that maps each valid input instance to the required output.
• Correctness: An algorithm must terminate and produce an output satisfying the problem specification for every valid input.
• Input size: Resource use is expressed as a function of a size parameter (n), such as the number of array elements, graph vertices, or input bits.
• Time complexity: Running time is estimated by counting elementary operations under a stated computational model.
• Space complexity: Memory use includes input storage, auxiliary data structures, and—in recursive algorithms—the call stack.
• Abstraction: Machine-dependent constants are usually suppressed so that growth rates can be compared as (n) becomes large.
• Design–analysis relationship: Data structures determine available operations, computational models assign their costs, and asymptotic analysis compares alternative algorithms.

II. Elementary Data Structures — Organizing and Accessing Data

A. Elementary data structures

Elementary data structures arrange values so that algorithms can store, retrieve, update, and traverse them efficiently.

• Array: A contiguous sequence (A[0],A[1],\ldots,A[n-1]) supporting indexed access.
  • Reading or writing (A[i]) takes (O(1)) time.
  • Searching an unsorted array takes (O(n)) time in the worst case.
  • Inserting at index (i) may require shifting as many as (n-i) elements.
• Linked list: A sequence of nodes in which each node stores a value and a link to the next node.
  • Accessing the (i)-th node takes (O(i)), hence (O(n)) in the worst case.
  • Insertion after a known node takes (O(1)).
  • A doubly linked list also stores a predecessor link, enabling movement in both directions.
• Stack: A last-in, first-out structure with push, pop, and top operations, each normally (O(1)).
  • Function calls use a call stack containing parameters, local variables, and return addresses.
• Queue: A first-in, first-out structure using enqueue and dequeue, normally in (O(1)) time.
  • A circular array avoids shifting elements after each removal.
• Tree: A hierarchical structure consisting of nodes and edges, with one root and no cycles.
  • In a balanced binary search tree, search, insertion, and deletion take (O(\log n)).
  • In a highly skewed tree, the same operations can deteriorate to (O(n)).
• Hash table: An array indexed through a hash function (h(k)), where (k) is a key.
  • Search and update take (O(1)) expected time under suitable hashing assumptions.
  • Collisions require techniques such as chaining or open addressing.
• Representation choice: The best structure depends on the dominant operation; arrays favor random access, while linked structures favor local insertion and deletion.

III. Computational Models — Assigning Costs to Operations

A. Basic computational models

A computational model specifies which operations are elementary and how their time and storage costs are measured.

• Random Access Machine model: The RAM model represents computation as instructions operating on registers and randomly addressable memory.
  • Arithmetic, comparison, assignment, branching, and memory access are usually assigned unit cost.
  • A loop executing one constant-time statement (n) times therefore has cost (an+b), where (a) and (b) are constants.
• Word-RAM qualification: A machine word contains (w) bits, commonly assuming (w \geq \lceil\log_2 n\rceil) so an input index fits in one word.
  • Operations on one word cost (O(1)).
  • Arbitrarily large integers cannot realistically be treated as constant-cost values.
• Comparison model: Algorithms gain information about keys only through comparisons such as (x<y).
  • Comparison sorting requires (\Omega(n\log n)) comparisons in the worst case.
  • Counting sort escapes this bound because it uses integer values as indices rather than relying only on comparisons.
• Pointer model: Data is accessed through references between records rather than unrestricted address arithmetic.
  • It naturally represents linked lists, trees, and graphs.
• Cost conventions: The model must remain consistent when algorithms are compared; treating multiplication as (O(1)) in one analysis and bit-dependent in another can invalidate the comparison.
• Model limitation: Unit-cost analysis abstracts away cache behavior, instruction pipelines, networks, and storage latency, so empirical performance can differ even when asymptotic bounds agree.

IV. Analysis of Algorithms — Behaviour Across Inputs

A. Analysis of algorithms: best-case, average-case, and worst-case behaviour

Case analysis distinguishes the minimum, expected, and maximum resources used among inputs of the same size.

• Cost function: Let (T(x)) be the operation count for input (x), and let (I_n) be the set of inputs of size (n).
• Best-case behaviour: The minimum cost is
  
  TEXT

    T_best(n) = min { T(x) : x ∈ I_n }.

  • Linear search has (T_{\text{best}}(n)=1) comparison when the target is the first element.
  • This bound may describe unusually favorable inputs rather than typical performance.
• Worst-case behaviour: The maximum cost is
  
  TEXT

    T_worst(n) = max { T(x) : x ∈ I_n }.

  • Linear search uses (n) comparisons when the target is absent or occurs last.
  • Worst-case bounds provide guarantees valuable in real-time and safety-critical systems.
• Average-case behaviour: Given probability (P(x)) for each (x\in I_n), expected cost is
  
  TEXT

    T_avg(n) = Σ T(x)P(x), for all x ∈ I_n.

  • If a successful linear-search target is equally likely to occupy any position, the expected comparisons are
    [
    \frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.
    ]
  • An average-case result is meaningful only when its input distribution is stated.
• Amortized distinction: Amortized analysis averages costs across an operation sequence, not across random inputs; dynamic-array append is (O(1)) amortized despite occasional (O(n)) resizing.
• Resource selection: Analyses may count comparisons, assignments, arithmetic operations, memory cells, or communication, depending on the computational setting.

V. Asymptotic Growth — Comparing Long-Run Efficiency

A. Asymptotic notations: big O notation

Asymptotic notation classifies resource functions by growth rate while ignoring constant factors and lower-order terms.

• Big (O)—upper bound: For nonnegative functions (f) and (g),
  
  TEXT

    f(n) ∈ O(g(n))

  
  when constants (c>0) and (n_0) exist such that
  [
  0\leq f(n)\leq c\,g(n)\quad\text{for every }n\geq n_0.
  ]
  Here (n) is input size, (c) is a constant multiplier, and (n_0) is the threshold beyond which the bound holds.
• Worked bound: For (f(n)=3n^2+5n+2), when (n\geq1),
  [
  3n^2+5n+2\leq3n^2+5n^2+2n^2=10n^2,
  ]
  so (f(n)\in O(n^2)) using (c=10) and (n_0=1).
• Big (\Omega)—lower bound: (f(n)\in\Omega(g(n))) if constants (c>0,n_0) exist such that (f(n)\geq c\,g(n)) for all (n\geq n_0).
• Big (\Theta)—tight bound: (f(n)\in\Theta(g(n))) when it is both (O(g(n))) and (\Omega(g(n))); thus (3n^2+5n+2\in\Theta(n^2)).
• Growth hierarchy: Common rates increase in the order
  [
  O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!).
  ]
• Interpretation: Big (O) does not automatically mean worst case; it can upper-bound best-, average-, or worst-case functions.
• Simplification rules: Constant factors are removed, lower-order terms are discarded, and sequential costs are added while nested independent loops generally multiply.

VI. Recursion — Solving Problems Through Smaller Instances

A. Recursion

Recursion defines a solution in terms of solutions to smaller instances of the same problem.

• Essential components:
  • Base case: Stops further calls and directly returns a result.
  • Recursive case: Reduces the input and combines the smaller result.
  • Progress condition: Ensures each call approaches a base case.
• Factorial example:
  
  TEXT

    FACTORIAL(n)
        if n = 0
            return 1
        return n × FACTORIAL(n - 1)

  
  For integer (n\geq0), this implements (n!=n(n-1)!) with (0!=1).
• Call stack: FACTORIAL(4) creates calls for (4,3,2,1,0); suspended calls return in reverse order, producing (1,1,2,6,24).
• Resource use: Factorial makes (n+1) calls, takes (\Theta(n)) time, and uses (\Theta(n)) stack space.
• Divide and conquer: Algorithms such as merge sort recursively solve multiple smaller subproblems and combine their results.
• Limitations: Missing base cases cause nontermination, insufficient input reduction causes infinite recursion, and deep recursion can overflow the call stack.
• Iteration comparison: Tail-recursive processes can often be rewritten as loops, reducing auxiliary stack space from (O(n)) to (O(1)) where tail-call optimization is unavailable.

VII. Recurrence Analysis — Measuring Recursive Algorithms

A. Recurrence relations to analyse recursive algorithms

A recurrence expresses the cost of a recursive algorithm using the costs of its smaller calls plus nonrecursive work.

• General divide-and-conquer form:
  [
  T(n)=aT(n/b)+f(n),
  ]
  where (a) is the number of subproblems, (n/b) is each subproblem’s size, and (f(n)) is division and combination work.
• Base condition: A recurrence must specify a constant-size case, commonly (T(1)=\Theta(1)).
• Substitution method: Guess a bound and prove it by induction after replacing smaller terms with the inductive hypothesis.
• Iteration method: Repeatedly expand the recurrence until reaching its base case.
  • For (T(n)=T(n-1)+1), expansion gives (T(n)=T(1)+(n-1)=\Theta(n)).
• Recursion-tree method: Represent recursive calls by levels and sum the work at each level.
  • Merge sort has (T(n)=2T(n/2)+\Theta(n)); every level costs (\Theta(n)), and there are (\log_2 n+1) levels, giving (\Theta(n\log n)).
• Master theorem: For (T(n)=aT(n/b)+f(n)), compare (f(n)) with (n^{\log_b a}).
  1. If (f(n)) is polynomially smaller, then (T(n)=\Theta(n^{\log_b a})).
  2. If the terms have equal order up to logarithmic factors, the result gains an additional logarithmic factor.
  3. If (f(n)) is polynomially larger and a regularity condition holds, then (T(n)=\Theta(f(n))).
• Applicability limits: The basic Master theorem does not directly handle unequal subproblem sizes, forms such as (T(n)=T(n-1)+T(n-2)), or irregular non-polynomial relationships; substitution or recursion trees may still apply.