Key Points

Empirical timing

• Tells you how long a program actually took, which is great.
• But the findings are specific to the experimental conditions (compiler options, computer, inputs tested, etc.).
• So we have to be careful how we extrapolate the findings to other conditions.

Operation counting

• Give the number of times a particular operation (or set of operations) occur as a function of some aspect of the input.
• Abstracts away all system-level issues (compiler, CPU, etc.)
• Allows us to weigh trade-offs in constant factors and lower-order terms.
• Requires us to make choices about what to count and what to account for in the input.
• Can be unnecessarily tedious/detailed for some questions.

Asymptotic analysis

• Answers the question “How well does this algorithm scale?” (e.g., what happens if we double the input size)
  • Technically, is focused on how the cost grows as the size of the input goes to infinity.
    • As a result we ignore constant factors and lower-order terms.
    • In practice conclusions about how costs grow are usually applicable to merely “large” sizes, not just infinite ones.
• Must useful when costs are fundamentally different (e.g., \(\Theta(n\) vs \(\Theta(n^2\)) rather than when they appear the same.
• \(f(n) \in \Theta(g(n))\) means that \(f\) and \(g\) are asymptotically similar.
  • \(f(n) \in \Theta(g(n))\) if and only if 0 < \(\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} < \infty\)
• Usually we compare a cost function to simple reference functions, sometimes called orders of complexity:
  • \(\Theta(1)\) — constant time
  • \(\Theta(\log n)\) — logarithmic time
  • \(\Theta(n)\) — linear time
  • \(\Theta(n \log n)\) — linearithmic time
  • \(\Theta(n^2)\) — quadratic time
  • etc.
• \(f(n) \in \textrm{O}(g(n))\) means that \(f\) is "no worse than" \(g\) in an asymptotic sense.
  • \(f(n) \in \textrm{O}(g(n))\) if and only if \(\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} < \infty\)
  • Example usage:
    • "In the worst case the complexity is \(\Theta(n)\) and in the best case it is \(\Theta(1)\), so the complexity is \(O(n)\)."
• The asymptotic notation family:
  • \(f(n) \in \textrm{o}(g(n))\), kind of like \(x < y\).
  • \(f(n) \in \textrm{O}(g(n))\), kind of like \(x \le y\).
  • \(f(n) \in \Theta(g(n))\), kind of like \(x = y\).
  • \(f(n) \in \Omega(g(n))\), kind of like \(x \ge y\).
  • \(f(n) \in \omega(g(n))\), kind of like \(x > y\).

Best case analysis

• What is the smallest number of operations for an input of size \(n\)?

Worst case analysis

• What is the largest number of operations for an input of size \(n\)?

Expected case analysis

• What is a "typical" number of operations?
• Three steps:
  • Break the outcomes into cases so that each case has the same complexity
  • Assign probabilities to the cases
    • Usually we assume a probability model that we think will help us understand the algorithm in practice.
    • A very common probability model is the "uniform probability" model which assumes every case is equally likely.
  • Find the expected complexity
    • A weighted sum of the complexities of the cases, weighted by probability.
    • \(\sum_{k} Pr(\textrm{Case}\ k)\textit{Cost}(\textrm{Case}\ k)\)

(When logged in, completion status appears here.)

Previous Page Next Page