Review Questions for Errors and Complexity

  1. What is the formula for relative error?
  2. What is the formula for absolute error?
  3. Which is usually the better way to calculate error?
  4. If you have k accurate significant digits, what is the tightest bound on your relative error?
  5. Given a maximum relative error, what is the largest (or smallest) value you could have?
  6. How do you compute relative and absolute error for vectors?
  7. What is truncation error?
  8. What is rounding error?
  9. What does it mean for an algorithm to take \(\mathcal{O}(n^3)\) time?
  10. Can you give an example of an operation that takes \(\mathcal{O}(n^2)\) time?
  11. What does it mean for error to follow \(\mathcal{O}(h^4)\)?
  12. Can you simplify \(\mathcal{O}(h^5 + h^2 + h)\)? What assumption do you need to make?
  13. If you know an operation is \(\mathcal{O}(n^4)\), can you predict its time/error on unseen inputs from inputs that you already have?
  14. If you are given runtime or error data for an operation, can you find the best \(x\) such that the operation is \(\mathcal{O}(n^x)\)?
  15. What is algebraic growth/convergence?
  16. What is exponential growth/convergence?