I'm having some trouble in understanding the different definitions for the rate of convergence of a sequence. I was playing around with following two functions, but even after experimenting for a while I'm still not really getting the point.
Consider the two functions $f(x) = \frac{1}{2^x}$ and $g(x) = \frac{1}{2^{2^x}}$. For $x \to \infty$ both converge to $0$. It's easy to show that $f$ converges linearly with rate $1/2$, whereas $g$ converges quadratically to $0$.
Now, here's a plot I made with MATLAB. I plotted both functions to the same figure to compare them.
We can see that $g$ is approaching its limit a little bit faster than $f$ (then again $g$ starts only from $1/2$ not $1$) , but the difference is not as dramatic as I was expecting. Even more confusing to me is the fact, that the graph of $f$ looks somewhat like a branch of a parabola whereas $g$ looks almost like a linear function (at least till about $x = 1.5$).
How can I make sense of this? Is there a way to plot these functions to exhibit the different rates of converges more clearly?
Best Answer
The linear scale in your plot obscures the fact that $g(x)$ is much smaller than $f(x)$ as $x$ gets large. For $x=5, f(x)=\frac 1{32}=0.03125, g(x)=\frac 1{2^{32}}=\frac 1{4294967296}\approx 2.33 \cdot 10^{-10}$ For larger $x$ the difference is even more pronounced. I don't know what definitions of linear and quadratic convergence you are using. I would have said that $f(x)$ converges exponentially to zero, which shows that it eventually becomes smaller than any inverse polynomial, and that $g(x)$ converges superexponentially to zero.
Here is a plot from Excel on a log scale. You can see that $g(x) \ll f(x)$ rather quickly.