CS210 · Annotated SlidesAnalysis — Algorithm Analysis
Analysis · Annotated slides

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.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up

Analysis of Algorithms

1
TipGrowth rates, slow → fast: 1 < log n < n < n log n < n² < n³ < 2ⁿ. Drop constants and lower-order terms.
Slide 2: Running time
Exam weight Low
    Slide 3: Measuring the running time
    Exam weight Low
      Slide 4: Measuring the running time
      Exam weight Low
        Slide 5: Measuring the running time
        Exam weight Low
          Slide 6: begian
          Exam weight Low
            Slide 7: Slide 7
            Exam weight Low
              Slide 8: a
              Exam weight Low
                Slide 9: 9000
                Exam weight Low

                  Limitations of Experiments

                  • It is necessary to implement the algorithm, which may be difficult
                  • Results may not be indicative of the running time on other inputs not included in the experiment.
                  • In order to compare two algorithms, the same hardware and software environments must be used

                  © 2014 Goodrich, Tamassia, Goldwasser

                  Analysis of Algorithms

                  Limitations of Experiments
                  10
                  Exam weight Low
                  1. Experiments need an implementation, depend on hardware/software, and can’t cover all inputs → theoretical analysis.

                  Challenges

                  • Experimental running times of two algorithms are difÞcult to directly compare unless the experiments are performed in the same hardware and software environments.
                  • Experiments can be done only on a limited set of test inputs; hence, they leave out the running times of inputs not included in the experiment (and these inputs may be important).
                  • An algorithm must be fully implemented in order to execute it to study its running time experimentally.
                  11
                  Exam weight Low

                    Goals of Algorithm analysis

                    1. Allows us to evaluate the relative efÞciency of any two algorithms in a way that is independent of the hardware and software environment.
                    2. Is performed by studying a high-level description of the algorithm without need for implementation.
                    3. Takes into account all possible inputs.
                    12
                    Exam weight Low
                      Slide 13: Running Time
                      Exam weight Low
                        Slide 14: Theoretical Analysis
                        Exam weight Low
                        1. Theoretical analysis: count primitive operations as a function of input size n; take the worst case.
                        Slide 15: Primitive Operations
                        Exam weight Low
                        1. Primitive operations: assignment, arithmetic, comparison, array index, method call, return.
                        Slide 16: n
                        Exam weight Low
                          Slide 17: Slide 17
                          Exam weight Low
                            Slide 18: Cost of basic operations
                            Exam weight Low
                              Slide 19: Cost of basic operations
                              Exam weight Low
                                Slide 20: Example: 1-S UM
                                Exam weight Low
                                  Slide 21: Seven Important Functions
                                  Exam weight High
                                  1. Seven functions: constant, log n, n, n log n, n², n³, 2ⁿ.
                                  TipGrowth rates, slow → fast: 1 < log n < n < n log n < n² < n³ < 2ⁿ. Drop constants and lower-order terms.
                                  🎯 How this can come up · 1 question
                                  MCQ

                                  Which grows fastest?

                                  Slide 22: Functions Graphed Using “Normal” Scale
                                  Exam weight Low
                                    Slide 23: i
                                    Exam weight Low
                                      Slide 24: Estimating Running Time
                                      Exam weight Low
                                        Slide 25: Growth Rate of Running Time
                                        Exam weight Low
                                        1. Changing hardware changes T(n) by a constant factor but not the growth rate.
                                        Slide 26: Why Growth Rate Matters
                                        Exam weight Low
                                          Slide 27: Practical implications of order-of-growth 2
                                          Exam weight Low
                                            Slide 28: Practical implications of order-of-growth
                                            Exam weight Low
                                              Slide 29: Practical implications of order-of-growth
                                              Exam weight Low
                                                Slide 30: Comparison of Two Algorithms
                                                Exam weight Low
                                                  Slide 31: Constant Factors
                                                  Exam weight Low
                                                    Slide 32: Big-Oh Notation
                                                    Exam weight High
                                                    1. f(n) is O(g(n)) if f(n) ≤ c·g(n) for all n ≥ n₀ (some positive c, n₀).
                                                    🎯 How this can come up · 2 questions
                                                    MCQ

                                                    7n − 2 is:

                                                    MCQ

                                                    3n³ + 20n² + 5 is:

                                                    Slide 33: Slide 33
                                                    Exam weight Low
                                                      Slide 34: fen
                                                      Exam weight Low
                                                        Slide 35: Slide 35
                                                        Exam weight Low
                                                          Slide 36: Slide 36
                                                          Exam weight Low
                                                            Slide 37: More Big-Oh Examples
                                                            Exam weight Low
                                                              Slide 38: Slide 38
                                                              Exam weight Low
                                                                Slide 39: Slide 39
                                                                Exam weight Low
                                                                  Slide 40: Big-Oh and Growth Rate
                                                                  Exam weight Low
                                                                  1. Big-Oh is an UPPER bound on the growth rate.
                                                                  Slide 41: imago
                                                                  Exam weight Low
                                                                    ★ Past exam

                                                                    Asymptotic Algorithm Analysis

                                                                    • The asymptotic analysis of an algorithm determines the running time in big-Oh notation
                                                                    • To perform the asymptotic analysis
                                                                      • We find the worst-case number of primitive operations executed as a function of the input size
                                                                      • We express this function with big-Oh notation
                                                                    • Example:
                                                                      • We say that algorithm arrayMax “runs in O (n) time”
                                                                    • Since constant factors and lower-order terms are eventually dropped anyhow, we can disregard them when counting primitive operations

                                                                    © 2014 Goodrich, Tamassia, Goldwasser

                                                                    Analysis of Algorithms

                                                                    42
                                                                    Exam weight High
                                                                    1. Asymptotic analysis: find the worst-case number of primitive operations, express it in Big-Oh.

                                                                    Asked in a real exam

                                                                    ★ Quiz 2 question bank · Big-O of each statement
                                                                    🎯 How this can come up · 2 questions
                                                                    MCQ

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

                                                                    MCQ

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

                                                                    Slide 43: Computing Prefix Averages
                                                                    Exam weight Low
                                                                      Slide 44: Prefix Averages (Quadratic)
                                                                      Exam weight Low
                                                                      1. prefixAverage1 recomputes each sum → 1 + 2 + … + n → O(n²).
                                                                      Slide 45: Arithmetic Progression
                                                                      Exam weight Low
                                                                        Slide 46: Prefix Averages 2 (Linear)
                                                                        Exam weight Medium
                                                                        1. prefixAverage2 keeps a running sum → O(n).
                                                                        🎯 How this can come up · 1 question
                                                                        Written

                                                                        Why is the second prefix-averages algorithm linear?

                                                                        Slide 47: Math you need to Review
                                                                        Exam weight Low
                                                                          Slide 48: Relatives of Big-Oh
                                                                          Exam weight High
                                                                          1. Big-Omega = lower bound; Big-Theta = tight bound (both upper and lower).
                                                                          🎯 How this can come up · 1 question
                                                                          MCQ

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

                                                                          Slide 49: Intuition for Asymptotic Notation
                                                                          Exam weight Low
                                                                            Slide 50: Example Uses of the Relatives of Big-Oh
                                                                            Exam weight Low
                                                                              Slide 51: Slide 51
                                                                              Exam weight Low
                                                                                Slide 52: Slide 52
                                                                                Exam weight Low
                                                                                  Slide 53: Slide 53
                                                                                  Exam weight Low