Algorithm analysis in the presence of undefined functions

I wonder how we can perform algorithm analysis when in an algorithm we have calls of functions whose definition we do not know, e.g. functions delivered by external libraries.

There are two ways to do this. If you're lucky, the implementer of the external library will have given you a runtime analysis of their code. If you're not, you can use an oracle model of computation. In a sense, this is treating the library routines as if they run in constant time. Of course, that would be ridiculous but an oracle-based analysis is a little smarter than that because it allows you to quantify how many times the oracle is accessed. For example, your answer might end up being something like, "The running time is $O(n^2)$ plus the cost of $O(\log n)$ calls to makeSausage() on instances of at most linear size."

StackExchange Computer Science Q#37922, answer score: 7