2
$\begingroup$

I have something of this kind:

$$(n-1) d m + m + 2m*v+2v^2 + v$$

Where all n,d,m,v are variables.

My little knowledge of computational complexity leads to do this kind of approximation:

$$ O( (n-1) d m + mv + v^2 )$$

However I feel I could further simplify into

$$ O( n d m + mv + v^2 )$$

and

$$ O( n d m + v^2 )$$

hence

$$ O(v^2)$$

Are my assumptions correct?

  • can I remove the $-1$ from $(n-1)$?
  • can I remove $mv$ since $v$ will grow $v^2$ any way?
$\endgroup$
6
$\begingroup$

You can remove the $-1$ from $(n-1)$, since $(n-1)dm=ndm-dm\leq ndm$. On the other hand, you can not simplify beyond $O(ndm+mv+v^2)$ unless you know more about the relations between the variables. $mv$ and $v^2$ are incomparable, depending on the ratio between $m$ and $v$ one may grow faster than the other. Similarly, your last step (removing $ndm$ in favor of $v^2$) is also incorrect.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.