I have been working with computing and numerical integration, and I have to juxtapose the operations required for Trapezoidal and Romberg for $n$ points to a certain error tolerance. For trapezoidal it is obviously $O(n)$. However, I am unsure of the operation count for Romberg, which i assume is either $O\left(n^2\right)$ or $O\left(2^n\right)$.

Can someone teach me what the operation count for Romberg integration is for $n$ points?

  • $\begingroup$ Wiki provides a good example with comparison $\endgroup$
    – gt6989b
    Commented Apr 20, 2020 at 16:20
  • 1
    $\begingroup$ I have read that before posting. It only comments on the stability and error. And my small brain can only comprehend it is at least approx. 3n $\endgroup$ Commented Apr 20, 2020 at 17:09


You must log in to answer this question.