Asymptotic Notation Manipulation

85 Views Asked by At

Say I have a double-indexed sequence $a(n,m)$, with $$∀ n, \quad a(n,m) = f(n) + o(g(m))$$ as $m→∞$ for some sequences $f,g$. Can I ever then conclude that $$a(n,n) \overset{?}{=} f(n) + o(g(n))$$ or for that matter, $a(n,h(n)) \overset{?}{=} f(n) + o(g(h(n)))$

Also, I suspect this is a no, but does anything change if I replace the sequences with functions on $ℝ$ and consider the continuous asymptotics?

1

There are 1 best solutions below

5
On BEST ANSWER

By definition, the expression

$$ a(n,m) = f(n) + o(g(m)) \qquad (m \to \infty) $$

means that there exists some function $b$ such that

$$ a(n,m) = f(n) + b(m) $$

and $b(x) = o(g(x))$ as $x \to \infty$. (It is specified in the comments that $b$ depends only on $m$.) So

$$ a(n,n) = f(n) + b(n), $$

and $b(n) = o(g(n))$ as $n \to \infty$, thus

$$ a(n,n) = f(n) + o(g(n)) \qquad (n \to \infty). $$

If $h(n) \to \infty$ as $n \to \infty$ then

$$ a(n,h(n)) = f(n) + b(h(n)) = f(n) + o(g(h(n))) \qquad (n \to \infty) $$

as well.

None of this changes if $n$ and $m$ are considered as continuous variables rather than just integers.