How to carry out arithmetics with Bachmann–Landau notations?

48 Views Asked by At

Here's something from my class.

As $n \to \infty$, $|\mathcal{F'}| = (1-o(1))\frac{n \choose t}{k \choose t} + o(1){n \choose t} = (1 + o(1))\frac{n \choose t}{k \choose t}$

I can sort of see why this makes sense, and I guess writing out the expression by the definitions would verify it. But is there an intuitive way to interpret this calculation and others similar to it?

2

There are 2 best solutions below

2
On BEST ANSWER

You can write the following estimate : $o(1){n \choose t} = o(1)\frac{{n \choose t}}{{k \choose t}}$, since $k$ and $t$ are fixed. Thus $|F'| = (1+o(1))\frac{{n \choose t}}{{k \choose t}} + o(1)\frac{{n \choose t}}{{k \choose t}} = \frac{{n \choose t}}{{k \choose t}} (1+o(1)+o(1)) = (1+o(1))\frac{{n \choose t}}{{k \choose t}}.$

You can interpret the notations $o$ and $O$ as : these are quantities whose names and exact values are not relevant, only their asymptotic behaviour.

1
On

Taking, for example, non negative case, we have following definitions: $O(g) = \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n > N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace $

$o(f)=\{g: \exists \epsilon, lim_{n \to \infty}\epsilon=0, \exists N, n>N, g=\epsilon \cdot f \}$

Firstly let me notice, that equality type $f=O(g)$ is quite different from type $O(f)=O(g)$. First means "$\in$", while under second many authors understand "$\subset$", though it should be said, that for most well known equalities we can understand it as "$\subset \land \supset$". Well known are following properties: $$C \cdot o(f)=o(f \cdot C)=o(f)$$ $$o(f)+o(f)=o(f)$$ First gives you possibility to change "minus" to "plus" in your first member and by second you obtain last equality.

As formal, so intuitive way, probably best, is think about brought above properties, as on both sides of the equality there are the same sets, simply written in different ways.

In the case of the expressed interest, I can write proof, that the equality holds exactly as in the case of sets i.e. right to left and vice versa "$\subset \land \supset$".