Question

How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails I take the limis of f'(x)/g'(x). But I'm not sure what to do in the following task (to prove whether the marked statement is true or not): enter image description here

Was it helpful?

Solution

There is an explicit formula for $\sum_{i=0}^n i^3$, but even without it, you can estimate $$ \int_0^n x^3 \, dx \leq \sum_{i=0}^n i^3 \leq \int_1^{n+1} x^3 \, dx. $$ Since $\int x^3 \, dx = x^4/4$, this shows that the sum is very close to $n^4/4$, and in particular is $\Theta(n^4)$.

(The explicit formula states that the sum equals $n^2(n+1)^2/4$.)

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top