CS210 · Analysis · Annotated SlidesAlgorithm Analysis
Original
Overview

Algorithm Analysis

Measuring running time experimentally and its limits, primitive operations and theoretical analysis, the seven important functions, growth rates, Big-Oh (and Big-Omega, Big-Theta), and the prefix-averages example (quadratic vs. linear). Quiz 2 asked for the Big-O of code statements.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 53 slides
  1. 1 Analysis of Algorithms
  2. 2 Running time
  3. 3 Measuring the running time
  4. 4 Measuring the running time
  5. 5 Measuring the running time
  6. 6 begian
  7. 7 Slide 7
  8. 8 a
  9. 9 9000
  10. 10 Limitations of Experiments
  11. 11 Challenges
  12. 12 Goals of Algorithm analysis
  13. 13 Running Time
  14. 14 Theoretical Analysis
  15. 15 Primitive Operations
  16. 16 n
  17. 17 iinssciswi.swasisst.sn
  18. 18 Cost of basic operations
  19. 19 Cost of basic operations
  20. 20 Example: 1-S UM
  21. 21 Seven Important Functions
  22. 22 Functions Graphed Using “Normal” Scale
  23. 23 i
  24. 24 Estimating Running Time
  25. 25 Growth Rate of Running Time
  26. 26 Why Growth Rate Matters
  27. 27 Practical implications of order-of-growth 2
  28. 28 Practical implications of order-of-growth
  29. 29 Practical implications of order-of-growth
  30. 30 Comparison of Two Algorithms
  31. 31 Constant Factors
  32. 32 Big-Oh Notation
  33. 33 w.c.sfens.sn
  34. 34 fen
  35. 35 Slide 35
  36. 36 not
  37. 37 More Big-Oh Examples
  38. 38 5511
  39. 39 ni von
  40. 40 Big-Oh and Growth Rate
  41. 41 imago
  42. 42 Asymptotic Algorithm Analysis
  43. 43 Computing Prefix Averages
  44. 44 Prefix Averages (Quadratic)
  45. 45 Arithmetic Progression
  46. 46 Prefix Averages 2 (Linear)
  47. 47 Math you need to Review
  48. 48 Relatives of Big-Oh
  49. 49 Intuition for Asymptotic Notation
  50. 50 Example Uses of the Relatives of Big-Oh
  51. 51 lognio
  52. 52 Slide 52
  53. 53 cn.zstcn.sn
Slide 1 / 53

Analysis of Algorithms

Slide 1: Analysis of Algorithms

Notes

  1. Tip Growth rates, slow → fast: 1 < log n < n < n log n < n² < n³ < 2ⁿ. Drop constants and lower-order terms.

Slide 2 / 53

Running time

Slide 2: Running time
Slide 3 / 53

Measuring the running time

Slide 3: Measuring the running time
Slide 4 / 53

Measuring the running time

Slide 4: Measuring the running time
Slide 5 / 53

Measuring the running time

Slide 5: Measuring the running time
Slide 6 / 53

begian

Slide 6: begian
Slide 7 / 53

Slide 7

Slide 7: Slide 7
Slide 8 / 53

a

Slide 8: a
Slide 9 / 53

9000

Slide 9: 9000
Slide 10 / 53

Limitations of Experiments

Slide 10: Limitations of Experiments

Notes

  1. Experiments need an implementation, depend on hardware/software, and can’t cover all inputs → theoretical analysis.

Slide 11 / 53

Challenges

Slide 11: Challenges
Slide 12 / 53

Goals of Algorithm analysis

Slide 12: Goals of Algorithm analysis
Slide 13 / 53

Running Time

Slide 13: Running Time
Slide 14 / 53

Theoretical Analysis

Slide 14: Theoretical Analysis

Notes

  1. Theoretical analysis: count primitive operations as a function of input size n; take the worst case.

Slide 15 / 53

Primitive Operations

Slide 15: Primitive Operations

Notes

  1. Primitive operations: assignment, arithmetic, comparison, array index, method call, return.

Slide 16 / 53

n

Slide 16: n
Slide 17 / 53

iinssciswi.swasisst.sn

Slide 17: iinssciswi.swasisst.sn
Slide 18 / 53

Cost of basic operations

Slide 18: Cost of basic operations
Slide 19 / 53

Cost of basic operations

Slide 19: Cost of basic operations
Slide 20 / 53

Example: 1-S UM

Slide 20: Example: 1-S UM
Slide 21 / 53

Seven Important Functions

Slide 21: Seven Important Functions

Notes

  1. Tip Growth rates, slow → fast: 1 < log n < n < n log n < n² < n³ < 2ⁿ. Drop constants and lower-order terms.

Exam angle

PredictionQ1

Which grows fastest?

Slide 22 / 53

Functions Graphed Using “Normal” Scale

Slide 22: Functions Graphed Using “Normal” Scale
Slide 23 / 53

i

Slide 23: i
Slide 24 / 53

Estimating Running Time

Slide 24: Estimating Running Time
Slide 25 / 53

Growth Rate of Running Time

Slide 25: Growth Rate of Running Time
Slide 26 / 53

Why Growth Rate Matters

Slide 26: Why Growth Rate Matters
Slide 27 / 53

Practical implications of order-of-growth 2

Slide 27: Practical implications of order-of-growth 2
Slide 28 / 53

Practical implications of order-of-growth

Slide 28: Practical implications of order-of-growth
Slide 29 / 53

Practical implications of order-of-growth

Slide 29: Practical implications of order-of-growth
Slide 30 / 53

Comparison of Two Algorithms

Slide 30: Comparison of Two Algorithms
Slide 31 / 53

Constant Factors

Slide 31: Constant Factors
Slide 32 / 53

Big-Oh Notation

Slide 32: Big-Oh Notation

Notes

  1. f(n) is O(g(n)) if f(n) ≤ c·g(n) for all n ≥ n₀ (some positive c, n₀).

Exam angle

PredictionQ1

7n − 2 is:

PredictionQ2

3n³ + 20n² + 5 is:

Slide 33 / 53

w.c.sfens.sn

Slide 33: w.c.sfens.sn
Slide 34 / 53

fen

Slide 34: fen
Slide 35 / 53

Slide 35

Slide 35: Slide 35
Slide 36 / 53

not

Slide 36: not
Slide 37 / 53

More Big-Oh Examples

Slide 37: More Big-Oh Examples
Slide 38 / 53

5511

Slide 38: 5511
Slide 39 / 53

ni von

Slide 39: ni von
Slide 40 / 53

Big-Oh and Growth Rate

Slide 40: Big-Oh and Growth Rate
Slide 41 / 53

imago

Slide 41: imago
Slide 42 / 53

Asymptotic Algorithm Analysis

Slide 42: Asymptotic Algorithm Analysis

Exam angle

PredictionQ1

for (i = 0; i < n; i++) for (j = 0; j < n; j++) sum++; is:

PredictionQ2

for (i = 1; i < n; i *= 2) sum++; is:

Slide 43 / 53

Computing Prefix Averages

Slide 43: Computing Prefix Averages
Slide 44 / 53

Prefix Averages (Quadratic)

Slide 44: Prefix Averages (Quadratic)

Notes

  1. prefixAverage1 recomputes each sum → 1 + 2 + … + n → O(n²).

Slide 45 / 53

Arithmetic Progression

Slide 45: Arithmetic Progression
Slide 46 / 53

Prefix Averages 2 (Linear)

Slide 46: Prefix Averages 2 (Linear)

Notes

  1. prefixAverage2 keeps a running sum → O(n).

Exam angle

PredictionQ1

Why is the second prefix-averages algorithm linear?

Compare with the model answer

It keeps a running total, adding one element per step instead of re-summing all earlier elements, so each of the n steps is constant time: O(n) instead of O(n²).

Slide 47 / 53

Math you need to Review

Slide 47: Math you need to Review
Slide 48 / 53

Relatives of Big-Oh

Slide 48: Relatives of Big-Oh

Notes

  1. Big-Omega = lower bound; Big-Theta = tight bound (both upper and lower).

Exam angle

PredictionQ1

f(n) is Θ(g(n)) means:

Slide 49 / 53

Intuition for Asymptotic Notation

Slide 49: Intuition for Asymptotic Notation
Slide 50 / 53

Example Uses of the Relatives of Big-Oh

Slide 50: Example Uses of the Relatives of Big-Oh
Slide 51 / 53

lognio

Slide 51: lognio
Slide 52 / 53

Slide 52

Slide 52: Slide 52
Slide 53 / 53

cn.zstcn.sn

Slide 53: cn.zstcn.sn