How do I use integral calculus to estimate a discrete sum?

Question

The Algorithms course I am taking on Coursera does not require discrete math to find discrete sums. Dr. Sedgewick recommends replacing sums with integrals in order to get basic estimates.

For example: $$\sum _{ i=1 }^{ N }{ i } \sim \int _{ x=1 }^{ N }{ x } dx \sim \frac { 1 }{ 2 } N^2$$

How would I go about doing this for the problem below?

What is the order of growth of the worst case running time of the following code fragment as a function of N?

int sum = 0; for (int i = 1; i <= N; i++) for (int j = 1; j <= i*i*i; j++) sum++;

What I've got so far:

$$\sum _{ i=1 }^{ N }{ } \sum _{ j=1 }^{ i^{ 3 } }{ } 1\approx \int _{ i=1 }^{ N }{ } dx\int _{ j=1 }^{ i^{ 3 } }{ } 1djdi$$

I'm not sure if this is correct, and I'm confused as to how to set these types of problems up. I've taken integral calculus, but it was almost 6 months ago. A hint in the right direction would go a long way.

Answer 1

The basic principle is the replace the summation variable with an integration variable.

$$\sum _{ i=1 }^{ N } i^k\approx \int _{ 0 }^{ N }{x^{k}}\operatorname dx = \frac{N^{k+1}}{k+1}$$

In this case you have a nested sum, so do a one-two step. $$\begin{align} \sum _{ i=1 }^{ N }\left( \sum_{j=1}^{i^3} 1\right) \approx & ~ \int_0^N \left( \sum_{j=0}^{x^3} 1\right)\operatorname d x \\ \approx & ~ \int _{ 0 }^{ N }\int_0^{x^3} 1\operatorname d y\operatorname dx \\ \approx & ~ \int _{ 0 }^{ N }x^3\operatorname dx \\ \approx & ~ \frac{N^4}4 \end{align}$$

Answer 2

It seems like the inner sum $\sum_{j=1}^{i^3} 1$ is easily seen to be $i^3$ (the sum of $i^3$ copies of $1$) and so what you are left with is $$\sum_{i=1}^N i^3 \approx\int_1^N x^3\,dx={x^4\over 4}\bigg|^N_1=(N^4-1)/4\approx N^4/4$$ I suppose you could also estimate $$\sum_{j=1}^{i^3} 1\approx \int_1^{i^3} 1\,dy=i^3-1$$ so the overall estimate becomes $$\int_1^N \int_1^{x^3} 1\,dy\,dx=\int_1^N (x^3-1)\,dx=\left({x^4\over 4}-x\right)\bigg|^N_1\approx N^4/4$$ but since the inner sum is so easy to calculate it hardly seems worth bothering to do this.

In what you wrote you were close but had an extra $di$, it seems. The general method is just replace each variable of summation (like $i$ and $j$) by a corresponding variable of integration, as in $$\sum_{i=1}^N \sum_{j=1}^{f(i)} g(i)\approx \int_1^N \int_1^{f(x)} g(y)\,dy\,dx$$ where $f$ and $g$ are suitable functions (in your case, $g(x)=1$ and $f(x)=x^3$).