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).
$\begingroup$
$\endgroup$
4
2 Answers
$\begingroup$
$\endgroup$
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}.$$
$\begingroup$
$\endgroup$
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}$".
norm. $\endgroup$