Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm wondering how to perform a worst case analysis on a such algorithm. The basic operation is function.

for (i=1; i<=N; i++)
    for (j=i; j<=i*i; j++)
        for (k=1; k<=N; k++)
            if (condition(i,j,k))
                b[i][k] = function (b[i][j]);
            else
                b[i][k] = b[j][k];

I don't know how to start and to justify my intuitions.
Does worst case analysis mean that I must assume that condition(x,y,z) will always be true and so I will execute function ?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

The innermost loop is executed $N$ times. The second innermost loop is exectued $\sum_{i=1}^N (i^2-i+1)$ times and the outermost loop is executed $N$ times. This yields a complexity of $O(N^4)$

share|improve this answer
    
How do you get the exponent of $5$? I count only $1+2+1=4$. –  Henning Makholm Oct 16 '12 at 16:36
    
I might be wrong but won't the summation lead to an additional N. ($\sum i^2 = \dfrac{N(N+1)(2N+1)}{6}$). –  Inquest Oct 16 '12 at 17:32
    
Yes, but if you do that summation, you shouldn't include another factor of $N$ for the outermost loop -- since that loop is exactly what the summation represents. –  Henning Makholm Oct 16 '12 at 17:34
    
@HenningMakholm. Perfect. Edited. I apologize for the mistake. –  Inquest Oct 16 '12 at 17:36
    
Thanks guys, I just don't understand how do you find out this result for the second innermost loop ? –  eouti Oct 16 '12 at 18:03

If condition is part of the input to the algorithm, then in the worst case it will return true every time, yes. (Think of the input being chosen by an adversary who want you to spend as much time executing your algorithm as he can make you).

However, if it is some fixed condition that you just haven't shown here, then considering the details of what the condition is, you may be able to get a better worst-case bound if you can show that it is true less than $\Omega(N^4)$ times.

share|improve this answer
    
No, condition might not be part of the input, it's just to show that there's a test performed I think. –  eouti Oct 16 '12 at 16:40
    
@eouti: In that case your analysis really ought to depend on the precise condition used, but you can still get a coarse worst-case analysis by assuming that it always returns true. –  Henning Makholm Oct 16 '12 at 16:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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