Running time and memory

If you cannot see the code of a function, but know that it takes arguments. Is it possible to开发者_JAVA技巧 find the running time speed and memory. If so how would you do it. Is there a way to use Big O in this case?

No, it's not possible to find either the memory or performance of a function by just looking at its parameters. For example, the same function

void DoSomething(int x, int y, int z);

Can be implemented as O(1) time and memory:

void DoSomething(int x, int y, int z) { }

or as a very, very expensive function taking O(x*y*z):

void DoSomething(int x, int y, int z)
{
  int a = 0;
  for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
      for (int k = 0; k < z; k++) {
        a++;
      }
    }
  }
  Console.WriteLine(a);
}

And many other possibilities. So, it's not possible to find how expensive the function is.

Am I allowed to run the function at all? Multiple times?

I would execute the function with a range of parameter values and measure the running time and (if possible) the memory consumption for each run. Then, assuming the function takes n argument, I would plot each data point on an n+1-dimensional plot and look for trends from there.

First of all, it is an interview question, so you'd better never say no.

If I were in the interview, here is my approach.

I may ask the interviewer a few questions, as an interview is meant to be interactive.

Because I cannot see the code, I suppose I can at least run it, hopefully, multiple times. This would be my first question: can I run it? (If I cannot run it, then I can do literally nothing with it, and I give up.)

What is the function used for? This may give a hint of the complexity, if the function is written sanely.

What are the type of argument? Are some they primitive types? Try some combinations of them. Are some of them "complex" (e.g. containers)? Try some different size combinations. Are some of them related (e.g. one for a container, and one for the size of the container)? Some test runs can be saved. Besides, I hope the legal ranges of the arguments are given, so I won't waste time on illegal guesses. Last, to test some marginal cases may help.

Can you run the function with a code? something like this:

start = clock();
//call the function;
end = clock();
time = end-start;

Being an interview question, you should never answer like "no it cannot be done".

What you need is the ability to run the code. Once you can run the code, call the same function with different parameters and measure the memory and time required. You can then plot these data and get a good estimate.

For big-O type notations also, you can follow the same approach and plot the results WRT the data set size. Then try to fit this curve with the known complexity curves like n, n^2, n^3, n*log(n), (n^2)*log(n) etc using a least square fit.

Lastly, remember that all these methods are approximations only.

no you cannot, this would have solved the Halting Problem , since code might run endlessly O(infinity). thus, solving this problem also solves HP, which is of course proven to be impossible.