0
$\begingroup$

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.

enter image description here

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Anyway, I doubt the question is answerable in its current form. What kind of answer do you want? How do you plan to use the answer? When you say "analysis", what do you mean by that? If you're looking for the asymptotic worst-case running time, you'll have to analyze the algorithm; that usually can't be found empirically/experimentally. See our reference questions for useful techniques: cs.stackexchange.com/q/23593/755 and cs.stackexchange.com/q/192/755. $\endgroup$
    – D.W. ♦
    Sep 11, 2016 at 23:24
  • $\begingroup$ @D.W. Edit complete, let me know if now makes more sense, $\endgroup$
    – Jesus Salas
    Sep 12, 2016 at 4:59
  • $\begingroup$ The second graph doesn't seem to show any significant change in the rate of growth as a function of $N$; it doesn't match the claims in the body text. So, you need to take a closer look. $\endgroup$
    – D.W. ♦
    Sep 12, 2016 at 5:40
  • $\begingroup$ @D.W. Probably is due the scale in the graph, not because there is no rate growth, just as you say is insignificant (ranges from 0,33 to 0,22), probably is ok to ignore the growth rate but I like to be accurate describing things, and it is there. $\endgroup$
    – Jesus Salas
    Sep 12, 2016 at 6:14
  • $\begingroup$ "My understanding that the algorithm has two different time complexities depending on the values of N and M." -- this sentence betrays multiple misconceptions. 1) No algorithm has a single "time complexity"; it depends on the machine model and cost function you choose. 2) Whichever cost function you fix, you get one. It may indeed depend on multiple parameters, but it remains a single function. Fixing one parameter and looking at the behaviour as the other grows is possible, but grossly oversimplifies the situation; it's like inspecting the real plane by walking only along the axes. $\endgroup$
    – Raphael ♦
    Oct 12, 2016 at 8:53

1 Answer 1

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.