2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step

I don't think that's really true. It seems to me that all you're doing here is observing that a discrete linear function changes by a constant amount at each step and wondering if that's connected to the fact that the derivative of a continuous linear function is constant. That doesn't have much to do with what linear-time algorithms necessarily do.

Since algorithms are intrinsically discrete and calculus is intrinsically about continuous properties, I'm not aware of any real relationships between them. One might occasionally use calculus, e.g., to bound a sum by an integral or in tricks like $$ \begin{align*} \sum_{i=1}^k in^i &= \sum_{i=1}^k (i+1)n^i - \sum_{i=1}^k n^i\\ &= \sum_{i=1}^k \frac{\mathrm{d}}{\mathrm{d}n}n^{i+1} - \sum_{i=1}^k n^i\\ &= \frac{\mathrm{d}}{\mathrm{d}n}\sum_{i=1}^k n^{i+1} - \sum_{i=1}^k n^i\,, \end{align*}$$ but I doubt that's the sort of application you had in mind.

$\endgroup$
2
$\begingroup$

A clear explicit relationship is that Big Oh is defined via limits which of course are central to calculus.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.