Why is $O(n^{km}+n^m)=O(n^{km})$?

88 Views Asked by At

I've seen this equation in one of my handouts $O(n^{km}+n^m)=O(n^{km})$, which doesn't seem obvious to me.

This is what I got trying to work it out:

$$\begin{align*}n^{km}+n^m &\leq C \cdot n^{km}\\ \frac{n^{km}+n^m}{n^{km}}&\leq C \\ 1+\frac{n^m}{n^{km}} &\leq C\\ 1+n^{m(1-k)} &\leq C\\ \end{align*}$$

But how can a constant be bigger than a polynomial?

1

There are 1 best solutions below

0
On BEST ANSWER

Assuming positive integral powers, then $k\geq1$, hence $1-k\leq0$, so that $$1+n^{m(1-k)}\leq2$$ for sufficiently large $n$.