1
$\begingroup$

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!

$\endgroup$

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
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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