Turning product of multiple variable factors with constants into Big-O

Question

I have a function which requires $(m+1)k(n+1)$ operations. How would I describe it in Big-O notation? I guess I need to keep the constants in $(m+1)$ and $(n+1)$ since they ensure that at best the complexity is $O(k)$ which is still not constant.

Answer 1

If you have no information about $k, m, n$, then the best you can do is $O(kmn + km + kn + k)$. I'll argue that you can have a case where each of the terms in this sum could dominate the others:

1. If $m, n = \frac{1}{\sqrt{k}}$, then you have $O(1 + \sqrt{k} + \sqrt{k} + k) = O(k)$.
2. If $n = m = k = w(1)$, then it should be $O(kmn)$.
3. If $m > 1, n = \frac{1}{m}$, then you have $O(k + km + \frac{k}{m} + k) = O(km)$.
4. You can construct similar to point 3 for the result to be $O(kn)$.