Error vs time complexity in big-O notation

39 Views Asked by At

I found two, apparently different uses of the big O notation:

  1. Describing the time complexity of an algorithm. For example, matrix multiplication time complexity is O(n^3) because the number of operations (and thus the computational time) goes as n^3 where n is the size of the matrices.
  2. Describing the truncation error in a function evaluation. For example, one can write the Taylor series as f(x+h)=f(x)+f'(x)h+O(h^2).

My question is how the two are related and are they possibly the same? Does it always mean that a higher order truncation error requires more computational time? How is the time complexity of a truncation algorithm related to its error?

0

There are 0 best solutions below