This question already has an answer here:

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!


marked as duplicate by Raphael Jan 21 '15 at 13:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $\sqrt{j}$ makes it hard to obtain a precise, closed form. When $n$ is sufficiently large, the result is approximately $O(n^{7/2})$. $\endgroup$ – hengxin Jan 21 '15 at 10:39

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


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


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)$.


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