BIG O In absence of enough information

Question

So, lets say you have a function, X(N) that is a total black box. You don't know the growth rate of the function, you can't look it up, and you can't view the source (at the moment).

Next lets examine it in the context of another function

for(int i = 0; i < N; ++i)
    X(N);

The code that you wrote is linear, yet clearly the function X has an impact of the growth rate of your function. If, for example, X(N) expands into for(int i = 0; i < N; ++i) your function is quadratic.

My question is this: If someone is asking what the Big O of your function is, what is the best way to describe the growth rate of your function?

I said I would call this linear, and the defense of my answer is the following.

If you knew the actual growth rate of X, you can give an accurate estimation of your code, yet while you can (in one way or another) get the code eventually, most functions don't come with performance statistics.

So if you did get access to the code of X, you could include it in your estimation, but where do you draw the line? X likely also calls other functions, which then call other functions. I feel that outside of manufactured scenarios where you are dealing with perfectly compartmentalized code, if you don't already know the growth rates of the black box functions being called you have to decide to estimate the code that you can.

Answer 1

If you would talk about drawing the line, I'd simply like to deliver like :-

The code's complexity :- O(N*o(X))

As soon as one get's to judge the complexity of the function X(N), one can simply substitute in the formula.

Till then, it will be a shorthand but useful notation all in all along with satisfying the loop's complexity.

Answer 2

You simply can't tell. There just isn't enough information. Saying that your function is linear is wrong unless X(N) is constant time.

You could, however, measure the time that X(N) takes to complete for different input sizes. Often this will give you a rough estimate of how it behaves asymptotically.