If I had a function call itself, meaning it is recursive, would that factor into the time complexity of the function? Or if I had a function call another function, would that factor into the total complexity of the outside function? I did find some information about the recursive types of functions in CRLS, but I could not fully understand nor find about a function calling another function. What is the reasoning we should or should not as well?
1 Answers
The call itself doesn't need to be considered to add any time, but calculations involving the parameters and the time needed to execute the function should.
Why? O-complexity doesn't care how you express a certain algorithmic idea. You could fully unroll your loops, use stacks or function calls - only the actual instructions matter. No cheating.
Related