# Big-O Notation and Calculus [closed]

I was wondering if there are any calculus relationships implicit in Big-O notation.

For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step, and also involves looking at each part of the input a constant number of times. The derivative of a linear expression is a constant expression, so there is some hint of a pattern. However, I haven't been able to figure out how to generalize these facts to other Big-O classes of algorithms.

Do derivatives/antiderivatives help in matching an algorithm's Big-O description with its behavior?

• This is more of a Computer Science question. And the answer is why would you do that? Generating the derivative would imply that you already have (or nearly have) the actual behaviour worked out. If you do this algebraically, it means you have the actual formula. If you do it empirically you've already sampled the actual graph of interest. The only occasion I surmise this might be effective is when you do not have any direct ability to analyse and are presented with integrals/derivatives. In which case yes but with caveats caused by derivative information loss. – Kain0_0 Aug 15 '19 at 1:02
• I think you're right, I'll try that site. As for why one might do that, I suppose for me it's simply to understand the concept of Big-O more precisely. – user10478 Aug 15 '19 at 15:31
• Big O actually has a very simple explanation that doesn't require calculus. It describes how a function scales as n increases. – Robert Harvey Aug 15 '19 at 16:13
• I am pretty sure someone can find an algorithm where calculating the order of growth correlates to some finite difference relationship. And such an equation may be solved using calculus. However, I have my doubts about any practical relevance. – Doc Brown Aug 19 '19 at 20:20