Thursday, 2 April 2015

limits - Is the function $f(n,m)=n^2+m^2$ in $O(nm)$

I am trying to solve a problem related to big o with two variables. I'll write the exercise below.



Prove or disprove the statement: $n^2+m^2=O(nm)$



Just in case, I'll write one definition needed:



Let $f,g:\mathbb N^k \to \mathbb N$, we say $f \in O(g)$ if and only if there are some numbers $c \in \mathbb N$ and $\overrightarrow{n_0} \in \mathbb N^k$ such that for all $\overrightarrow{n} >\overrightarrow{n_0}$,$$f(\overrightarrow{n}) \leq cg(\overrightarrow{n})$$



where $\overrightarrow{n_1} > \overrightarrow{n_2}$ if and only if $n_{1_i} > n_{2_i}$ for all $i=1,...,k$.




I think that this statement is false but I couldn't write a formal proof of this. I would really appreciate any suggestions. Thanks in advance.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...