1
$\begingroup$

On calculating the convexity of an optimization problem, I am getting a term $O(\sqrt{n+m}(n)^3)$. Here both $m$ and $n$ are parameters. Is there any way I can simplify this term to write it as a product?
I know that if time complexity $T(n,m)=O(\sqrt{n+m}(n)^3)$, then $\exists C,M $ such that $\vert T(n,m) \vert \leq C\vert \sqrt{n+m}(n)^3 \vert $ when either $n,m \geq M$. I need the simplification for the interpretation of the algorithm. (Like, if time complexity is $O(n)$, then if $n$ is multiplied by 10, then the time complexity is also multiplied by 10. But it seems such an interpretation is not possible in the above case, as $m$ and $n$ are independent terms in summation).

$\endgroup$
4
  • $\begingroup$ As $\sqrt{n}<n^3\sqrt{n+m}$ and $\sqrt{m}<n^3\sqrt{n+m}$, then you cannot estimate $n^3\sqrt{n+m}$ with upper bound dependent only on one variable. $\endgroup$
    – zkutch
    Commented Jun 21, 2022 at 21:40
  • $\begingroup$ I assume that $n/m$ means "both $n$ and $m$", and not the quotient ? $\endgroup$
    – user16034
    Commented Jun 22, 2022 at 8:40
  • $\begingroup$ @YvesDaoust I meant n or m. $\endgroup$ Commented Jun 22, 2022 at 8:57
  • $\begingroup$ Better write $n,m\ge M$. (And I doubt that the or interpretation be correct.) $\endgroup$
    – user16034
    Commented Jun 22, 2022 at 9:12

2 Answers 2

1
$\begingroup$

Presumably you are after a substitution like$$\sqrt{n+m}\,n^3\le f(n)\,g(m),$$ or equivalently

$$n+m\le p(n)\,q(m).$$

If you freeze $m$, then $p(n)=\Omega(n)$ must hold (and similarly $q(m)=\Omega(m)$). So I see no better solution than

$$\sqrt{n+m}\,n^3\le\sqrt{nm}\,n^3= n^{7/2}m^{1/2}.$$

$\endgroup$
1
$\begingroup$

If you multiply $m$ by $10$, the magnitude of the term varies by a factor

$$\sqrt{\frac{n+10m}{n+m}}=\sqrt{\frac{\frac nm+10}{\frac nm+1}}.$$

That factor stays in range $\left(1,\sqrt{10}\right)$ and varies relatively little as a function of $\frac nm$.

If you multiply $n$ by $10$, the magnitude varies by $1000$ times a similar factor.

So it is not very wrong to explain the complexity as "roughly $n^{7/2}$".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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