Algorithm Time complexity analysis for algorithm having two different time complexities

Question

I'm implementing an algorithm that analyze several properties on large set of integers, the time complexity is bound to $N$ (set length) and $M$ (bits to represent the numbers). I'm having some trouble to figure out how to express its time complexity because I don't know how to handle next situation:

The asymptotic analysis establish that when $N$ is constant and $M$ grows the operations count grows at constant rate ($R1$) until it reaches a threshold that depended on the value of $N$, then the operations count does not grow anymore.

On the other hand when $M$ is constant and $N$ grows the operations count grows also at constant rate ($R2$) until it reaches a threshold that depends on the value of $M$, then, it continues growing but at a slower rate.

My understanding that the algorithm has two different time complexities depending on the values of $N$ and $M$.

Is there any way to integrate this behavior in a single Big-Oh expression?

And if not possible, how will be the right way to describe the time complexity for an algorithm with these properties?

Answer 1

No, you can't determine the asymptotic worst-case running time from these two graphs.

First, plotting empirical running times is not a reliable way to determine worst-case running time: How to fool the plot inspection heuristic?. So, the approach of graphing performance on some testcases isn't a reliable way to get a "big-O" running time.

Second, knowing just these two graphs isn't enough to uniquely determine how it depends as a function of both $N,M$. There are multiple possibilities for functions $f(N,M)$ that are consistent with both of these graphs. For example, a two-variable function $f(N,M)$ is not uniquely determined by the one-variable functions $f(100,M)$ and $f(N,100)$.

Third, I strongly suspect that those two graphs don't tell the whole story. For instance, you show us only a single graph for when $N$ is held constant and $M$ is varied. But I suspect the shape of the graph (or the slope of the line) might depend on exactly which constant value of $N$ you choose: a very large value of $N$ might lead to a different graph than a small value of $N$. This further highlights that we don't have enough information to uniquely infer the running time.

---

So what should you do? Rather than plotting running times and treating the algorithm as a black box, it's probably to start by looking at the algorithm itself. Look at the pseudocode of the algorithm and analyze its worst-case running time using standard techniques. See, e.g., Is there a system behind the magic of algorithm analysis? and How to come up with the runtime of algorithms?. This allows mathematically rigorous analysis that is provably correct and that can analyze the running time for all combinations of $N,M$.