Complexity of an Algorithm

Question

I have an algorithm which calculates $(m+1)\cdot (n+1)$ elements (one in each cycle), where $m$ and $n$ are given in the input. Would you say that the complexity of this algorithhm is $O(mn)$ or $O(m^2)$, supposing $m>n$, or maybe simply $O(mn+m+n+1)$?

Answer 1

You would go for $O((m+1)\cdot (n+1)) = O(m\cdot n)$. You can estimate that with $O(m^2)$ if you happen to know that $m>n$, but note that this might be a far shot. For example, $m$ might have been calculated as $n^3$, so $O(m^2) = O(n^6)$, which is much bigger then $O(m \cdot n) = O(n^3 \cdot n) = O(n^4)$. So do this estimation only if you have to.