Turning product of multiple variable factors with constants into Big-O 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.
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:


If $m, n = \frac{1}{\sqrt{k}}$, then you have $O(1 + \sqrt{k} + \sqrt{k} + k) = O(k)$.
If $n = m = k = w(1)$, then it should be $O(kmn)$.
If $m &gt; 1, n = \frac{1}{m}$, then you have $O(k + km + \frac{k}{m} + k) = O(km)$.
You can construct similar to point 3 for the result to be $O(kn)$.
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:


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