Complexity of nested loops [duplicate]

Question

This question already has answers here:

Is there a system behind the magic of algorithm analysis? (3 answers)

Closed 10 years ago.

I'm trying to figure out the complexity of the following algorithm.

for(int i=1; i <= N; i++)
 for(int j=1; j <= i; j++)
 for(int k=1; k <= i*sqrt(j); k++)

I'm trying to figure it out using a method similar to rizwanhudda's solution in this similar question. I'm having some trouble though because the innermost loop references both i and j. Can somebody translate this problem into something similar to rizwanhudda's approach (ie count the number of triplets (i, j, k))? Thanks!

• hengxin: $\sqrt{j}$ makes it hard to obtain a precise, closed form. When $n$ is sufficiently large, the result is approximately $O(n^{7/2})$.

Answer 1

I'm not convinced the approach translates well. In particular, the last statement would become something like "the square root of the number of boxes [...]" and that doesn't work out well. A more traditional way to approach this is:

The inner loop has complexity $\Theta(i\sqrt{j}))$. This loop is executed for 1ドル\leq j \leq i$ (middle loop) which gives a complexity of

$\Sigma_{j=1}^i i\sqrt{j}=i\Sigma_{j=1}^i \sqrt{j}$

Evaluating $\Sigma_{j=1}^i \sqrt{j}$ is tricky. There is no closed-form formula, but we can obtain an approximation by changing the sum to an integral. Note that

$\int_0^i x^{1/2}=\frac{2}{3}i^{3/2}$

is a lower bound, while

$\int_1^{i+1} x^{1/2}=\frac{2}{3}{i+1}^{3/2}-\frac{3}{2}$

is an upper bound. We may conclude that

$\Sigma_{j=1}^i \sqrt{j}=\Theta(i^{3/2})$.

Hence the middle loop has complexity $\Theta(i^{5/2})$. For the outer loop, we have to evaluate

$\Sigma_{i=1}^n i^{5/2}$

for which there is once again no closed-form formula. By applying the same integral technique, we find that the complexity is

$\Theta(n^{7/2})$.

However, finding a closed-form formula for the exact complexity (without asymptotic notation) is impossible.

Answer 2

An easy form of deciding the $O$ for your problem is: Think the second and the third loop is just $N$ and what you did there is just an optimization, this way you'll have $O(n^3)$ which I believe most approximates it. Once $N$ is big enough($\infty$), your algorithm will surely converge near $O(n^3)$.