I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows :

\begin{eqnarray} \mathcal{O}(3m+2 m\cdot n\cdot p+p\cdot(n+m)) &=& \mathcal{O}(m\cdot(3+2n\cdot p)+p\cdot(n+m))\\ &=& \mathcal{O}(2m\cdot n\cdot p+n\cdot p + m\cdot p)\\ &=& \mathcal{O}(n\cdot p \cdot(2m+1) + m\cdot p)\\ &=& \mathcal{O}(2n\cdot m \cdot p + m\cdot p)\\ &=& \mathcal{O}(m \cdot p\cdot(2n+1))\\ &=& \mathcal{O}(2n\cdot m \cdot p)\\ &=& \mathcal{O}(m\cdot n \cdot p)\\ \end{eqnarray}

I successively replace $3+2n\cdot p$ by $2n\cdot p$, $2m+1$ by $2m$ and $2n+1$ by $2n$ since they are asymptotically equivalent. Is it correct?

More generally can I always replace any subexpression with an asymptotically equivalent one within the big-O expression?


All is correct, but - it can be done in one step after you represent this expression as a sum of terms: $$\mathcal{O}(3m+2m⋅n⋅p+p⋅n+p⋅m)=\mathcal{O}(m⋅n⋅p)$$ because:

  • The term $(m⋅n⋅p)$ dominates all the other terms - $(3m)$, $(p⋅n)$, and $(p⋅m)$ - in this sum.
  • Constants are eliminated according to the $\mathcal{O}$ definition.
| cite | improve this answer | |

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.