Complexity bound for a quadratic convergence method

28 Views Asked by At

Let us define $r_k = \|x_k-x^*\|$, where $x_k$ is the solution of the $k$th iteration and $x^*$ is the optimal solution. And we know a algorithm converges like $r_{k+1} = c r_k^2$, where $c$ is a constant. In the book of "Introductory Lectures on Convex Programming", it said that the complexity bound for the algorithm is $\ln \ln \xi$, where $\xi$ is the desired accuracy. Can someone help to understand why the complexity bound is $\ln \ln \xi$? Thanks in advance!