1
$\begingroup$

I am working on an algorithm in which one parameter $a(t)$ verifies the following asymptotic limit: $f(a(t))=\mathcal{O}(1/t^{2})$. I am using it to assess an empirical rate of convergence of $f(a(t))$ as $\frac{f(a(t))}{f(a(10t))}\approx100$. It works more or less well, but I know that mathematically it is not formal. Do you have any suggestion on how to compute $\frac{f(a(t))}{f(a(10t))}$ from the asymptotic limit?

$\endgroup$

1 Answer 1

0
$\begingroup$

$f(a(t))=O(1/t^2)$ means that $f(a(t))=\frac{g(t)}{t^2}$, $g$ being a bounded function. So $$\frac{f(a(t))}{f(a(10t))} = \frac{\frac{g(t)}{t^2}}{\frac{g(10t)}{100t^2}} = 100\frac{g(t)}{g(10t)}$$ Problem is, you have to know both bounds for $g$ to make this accurate. If you know $$(\forall t)\ 0<A\le g(t)\le B$$ which is quite common in algorithms theory, then $$\frac{f(a(t))}{f(a(10t))} \le \frac{100B}{A}$$ But in general, you can not find any good bound (and this bound may not exist).

$\endgroup$
2
  • $\begingroup$ Thanks @Nicolas FRANCOIS, in this particular case, $f(a(t))\leq \frac{C}{t^{2}}$. Could we use 100 as an upper bound for $\frac{f(a(t))}{f(a(10t))}$? $\endgroup$
    – Gaussian
    Dec 17, 2020 at 19:08
  • $\begingroup$ No we can't, because you need a lower bound also (inequalities are reversed for quantities appearing at denominator). $\endgroup$ Dec 17, 2020 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.