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