Algorithmic Analysis – Lecture 2 Notes

Outline of the Lecture

• 8 major blocks covered
  • Overview
  • Fundamentals
  • Asymptotic Complexity
  • Analysing Non-recursive Algorithms
  • Analysing Recursive Algorithms
  • Empirical Analysis
  • Rule-of-thumb/Approximate Estimation
  • Summary & next steps

Motivation & Learning Outcomes

• Practical scenario: choosing the faster of two ways to search an unordered medicine stock (sequential vs. sort-then-search)
  • Highlights the need to estimate running time before implementation
• Outcomes targeted in Chapter 2 of Levitin’s textbook:
  • Measure and compare algorithmic complexity classes
  • Analyse non-recursive and recursive code
  • Perform empirical evaluations
  • Appreciate why time is the primary focus (space analysis treated elsewhere)
  • Ethical angle: deploying a costly algorithm can waste computing resources and energy

Fundamentals: Basic Operations & Input Size

• Basic operation
  • The unit‐cost step dominating total time
  • Examples: comparison, addition, multiplication, assignment, array access
  • Often “the most frequently executed” but may change if certain ops are slower (e.g., division)
• Input size (n)
  • Problem-dependent measure (array length, matrix dimension, # vertices, etc.)
  • All counts of basic operations are expressed as functions of n
• Core time estimate t(n) \approx c_{op}\times C(n)
  • c_{op} = actual execution time of one basic op
  • C(n) = number of executions as a function of n

Running Example 1 – Power Computation a^n

• Pseudo-code shows a single for-loop with one multiplication
• Basic op = multiplication, input size = n
• C(n)=n \Rightarrow t(n)=c_{op}\,n ⇒ linear

Running Example 2 – Sequential Search

• Best case: key in first slot ⇒ C_b(n)=1
• Worst case: key absent ⇒ C_w(n)=n
• Average case: if success probability = p C_{avg}(n)=p\,\frac{n+1}{2}+n(1-p)
  • p=1\Rightarrow (n+1)/2, p=0\Rightarrow n
• Illuminates difference between best/worst/average notions vs. asymptotic bounds

Runtime-Complexity Vocabulary

• Worst-, best-, average-case defined formally over all possible inputs of size n
• Important note: average case ≠ (best + worst)/2

Asymptotic Complexity & Equivalence Classes

• Need common language to compare diverse t(n) expressions
• Upper bound (Big-O)
  • Informal: t(n) \in O(g(n)) if g(n) grows at least as fast for large n
  • Formal: \exists c>0, n0: t(n)\le c\,g(n)\ \forall n\ge n0
• Lower bound (Big-Ω)
  t(n) \in \Omega(g(n)) \iff \exists c>0, n0: t(n)\ge c\,g(n)\ \forall n\ge n0
• Tight bound (Big-Θ) – simultaneously O and Ω
• Common equivalence families (after stripping constants & lower-order terms)
  • O(1) constant
  • O(\log n) logarithmic (binary search)
  • O(n) linear (sequential scan)
  • O(n\log n) linearithmic (merge sort)
  • O(n^2) quadratic (selection sort)
  • O(2^n) exponential (subset generation)
  • O(n!) factorial (permutation generation)
• Guideline to simplify g(n)
  1. Drop additive constants: 0.01n-6 \rightarrow 0.01n
  2. Keep highest-order term only: n^3+n^2+n \rightarrow n^3
  3. Ignore coefficient: 7n^3 \rightarrow n^3

Example Simplification

• Given g(n)=2n^4+43n^3-n+50 ⇒ O(n^4)

Analysing Non-Recursive Algorithms – 4-Step Method

1. Choose input-size measure
2. Identify basic operation
3. Express C(n) via a summation that mirrors loop nests; use series identities
4. Convert t(n)=c_{op}C(n) to tight asymptotic bound

Example – a^n revisited

• Summation \sum_{i=1}^{n}1=n ⇒ O(n)

Example – Matrix Addition (n × n)

• Two nested loops
  C(n)=\sum{i=0}^{n-1}\sum{j=0}^{n-1}1=n^2 ⇒ O(n^2)

Analysing Recursive Algorithms – 5-Step Method

1. Input size
2. Basic operation
3. Write recurrence for C(n) with base case(s)
4. Solve recurrence (backward substitution, Master theorem, etc.)
5. Deduce t(n) and asymptotic class

Example – Recursive Factorial

• Recurrence: C(n)=C(n-1)+1,\ C(1)=0
• Backward substitution pattern: C(n)=C(1)+(n-1)=n-1
• Thus t(n)=c_{op}(n-1)\in O(n)

Empirical (Experimental) Analysis

• Complements theory; exposes constant factors and implementation overheads
• 7-step experimental protocol
  1. Clarify purpose (compare, validate, tune?)
  2. Select metric M (wall-clock time, instruction count, cache misses…)
  3. Define input domain & sizes
  4. Implement algorithms faithfully
  5. Generate input instances (random, adversarial, realistic)
  6. Run experiments & collect data
  7. Analyse (plots, statistical summaries, regression to g(n))

Benchmarking Examples

• Sorting 2 500 random items
  • Empirical times: Quick-sort ≈ 1.3 s; Merge-sort ≈ 8.1 s; Selection-sort ≈ 35 s despite same O(n\log n) class for first two
  • Input order matters: Quick-sort degrades to 35 s on already-sorted list (near worst-case pivot choices)
• Search
  • For n\le 10^3 linear scan may beat binary search due to setup cost; by n\approx10^6 the \log n advantage dominates

Rule-of-Thumb / Approximate Complexity Estimation

• Experience-based heuristics before formal proof
  • Single simple loop ⇒ usually O(n)
  • Two nested loops over same range ⇒ O(n^2)
  • Constant-time array or hash access ⇒ O(1)
• Must confirm via analysis or measurement

Quick Reference

• Constant O(1): direct indexing, pointer swap
• Linear O(n): full scan, list copy
• Quadratic O(n^2): all pairs, naive duplicate search

Connections & Practical / Ethical Implications

• Builds on Lecture 1 foundations (definition of algorithms); prepares for paradigm modules (brute force next week)
• Energy & sustainability: algorithms with higher-order growth waste CPU cycles → larger carbon footprint
• Software engineering: deciding early prevents costly refactors and under-provisioned systems in production

Summary & Next Steps

• Core toolkit established: basic op, input size, t(n), asymptotic classes, recurrence solving, empirical design
• Able to choose faster algorithm in real scenarios (medicine search example)
• Upcoming: study brute-force paradigm and continue refining estimation skills