1

I'm taking my first numerical analysis course. I'm trying to understand the difference between order of convergence and Big O notation (asymptotic order). If I have two algorithms and algorithm A is Big O of $h$ while algorithm B is Big O of $h^2$ I understand that algorithm B is faster. However, isn't algorithm B's order of convergence also 2 (from exponent in h^2)?

If I am mistaken here can someone help me understand the difference between order of convergence and Big O notation (asymptotic order)?

Thanks,

-Idle

Idle Fool
  • 1,022

1 Answers1

2

What is $h$ in relation to your hypothetical algorithm? That should almost automatically answer your question.

In case $h$ is some measure of the fineness of the discretization, it makes sense to measure the approximation error quality as $O(h^p)$ and call $p$ the approximation order (usually of some kind of integration).

In the case of iterative root-finding algorithms, you can measure how fast the distance goes to zero from step to step, there you can check if $|x_{n+1}-x_*|=O(|x_n-x_*|^p)$, or in the case of simple roots $f(x_{n+1})=O(|f(x_n)|^p)$, where $p$ is then called the order of convergence.

As you notice, the described situations are rather different.

Lutz Lehmann
  • 126,666
  • hmm, I have a notion of what order of convergence is. My instructor explains it like...if the order of convergence is 2 every step toward the root takes 4 steps (I think that's right). i.e. We go to the root faster. Can you give me something this tangible for Big O notation? The concept seems very nebulous to me. Thanks in advance. -Idle – Idle Fool Oct 15 '17 at 19:34