# Big O and Little O

If $$a_n = O(n^\alpha)$$ and $$b_n = o(n^\beta)$$, prove that $$a_nb_n = o(n^{(\alpha + \beta)})$$ and $$a_n+b_n = O(\max(n^\alpha, n^\beta))$$.

For the part about $$a_nb_n = o(n^{(\alpha + \beta)})$$, I get that I am supposed to set it up so that

$$|a_n| < Mn^\alpha$$ for some positive real M for $$n \geq n'$$

$$|b_n| < \epsilon n^\beta$$ for all positive reals $$\epsilon$$ for $$n \geq n''$$

Then I choose the maximum of n' and n'', and I get

$$|a_nb_n| < M\epsilon n^\alpha n^\beta$$.

My question is does this finish the proof? If there is a positive real M multiplied by $$\epsilon$$, does that map to all $$\epsilon$$? How do you denote this? I think this is some real analysis proof here or I can just say a constant multiplied by epsilon is just epsilon?

For the sum proof, does it become big-O rather than little-O because it cannot be mapped to $$\epsilon$$ when you add the two parts?

Thank you in advance for the help.

• For the second part, if $\beta > \alpha$ then you do get $o(n^\beta)$, but otherwise, all you can conclude is $O(n^\alpha)$. Nov 1 '20 at 19:16
• Ok thank you, that makes sense. For the first part, is it valid to say something like $\epsilon$ times a constant will result in $\epsilon$? Like this is true from just logic, but I don't know if there's some math theorem I need to state.
– Alex
Nov 1 '20 at 19:40
• Use the definitions. That's all you need to know. Nov 1 '20 at 19:40

For $$a_n$$ you use correct definition i.e. $$a_n \in O(n^\alpha)$$: $$\exists C>0, \exists N_1 \in \mathbb{N}, \forall n>N_1, |a_n| \leqslant C n^\alpha$$.
For little-$$o$$ for $$b_n \in o(n^\beta)$$ let's use following definition : $$\exists \varepsilon_n, \lim\limits_{n \to \infty}\varepsilon_n=0$$ and $$\exists N_2 \in \mathbb{N}$$ such that $$\forall n>N_2, b_n=\varepsilon_n n^\beta$$.
So, taking $$n>\max(N_1,N_2)$$ we have $$a_n \cdot b_n= \frac{a_n \varepsilon_n}{n^\alpha} \cdot n^{\alpha+\beta} = \phi_n n^{\alpha+\beta}$$. We need to prove, that $$\phi_n \to 0$$: $$|\phi_n| = |\frac{a_n \varepsilon_n}{n^\alpha}| \leqslant C |\varepsilon_n|\to 0$$.
• Thanks I understand this. I have a small question. When you rewrote like the little-o notation, what happened to like the absolute value part of |bn|. In general, why is there an absolute value part for the definition of |an| to begin with? Furthermore, when you showed $\phi_n$ -> 0, you took the absolute value of it, but your definition of little-o didn't have the $\epsilon$ as an absolute value, so why do you need to consider the absolute value later. Thanks.
• In general definition of little-$o$ do not need absolute value. Estimation for absolute value is result of representation $b_n=\varepsilon_n n^\beta$. As to second question, then $\phi_n \to 0$ is same as $|\phi_n| \to 0$ and in latter we use estimation for absolute value for $a_n$. Nov 1 '20 at 23:04