Runtime analysis of functions that call other functions

Question

If you have a function being called in another function, do you figure out the runtime for the being called and then "add" that to function you wish to analyze the runtime for?

Function to be analyzed:

for (i = 0, i > n, ++i)
{
    if (function.call() > 0)
    {
        \\something
    }
}

Function called:

Call
{
   for (i = 0, i > n, ++i)
    {
        \\return something
    }
}

Answer 1

Think of it as some kind of accounting.

The inclusive time of a function is:

• The elapsed time between the entrance and the exit of this function,
• MINUS pure overhead (if known; zero if negligible or undetermined)
• PLUS total elapsed time spent on other CPU cores or OS threads due to any work that is delegated by this function. (In other words, external work that is "billable" to this function.)

The exclusive time of a function is:

• The inclusive time of the function,
• MINUS the total inclusive time of all children of that function.
  • The definition of "children" is up to the profiler designer.
  • For example, child functions which have been completely inlined into the parent function are usually no longer considered to be a separate item, and thus will not be subtracted.
  • On the other hand, any use of "source-based" profiler frameworks will impede the inlining optimization by the compiler, to the point that any functions marked for instrumentation will never be inlined anyway.

Answer 2

@Rufflewind had it right in the comments, you have to substitute the function call - think closer to copy/pasting the subfunction into the main function. This can get a bit nasty when you have recursive calls, as you might guess.

One important thing to keep in mind is the "what" of your analysis. Usually big-O style runtime analysis picks a certain number of operations to measure - swaps, additions, multiplications, etc. You may have cases where the subfunction does work, but none of the operations being measured, in which case it should drop out of analysis.

So it looks like in your example that the outer loop would be O(N) if the subfunction did "no work", but when you substitute it, you'll end up with some O(N^2) type of operation.