0
$\begingroup$

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 ?

2 Answers 2

1

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

  • 0
    How do you get the exponent of $5$? I count only $1+2+1=4$.2012-10-16
  • 0
    I might be wrong but won't the summation lead to an additional N. ($\sum i^2 = \dfrac{N(N+1)(2N+1)}{6}$).2012-10-16
  • 0
    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.2012-10-16
  • 0
    @HenningMakholm. Perfect. Edited. I apologize for the mistake.2012-10-16
  • 0
    Thanks guys, I just don't understand how do you find out this result for the second innermost loop ?2012-10-16
  • 0
    How I thought about it was to imitate the computer and find a pattern among the numbers: The first time the loop executes, it will run when i is 1 to i is <=1 (which is once), next time from 2 to 4 (which is thrice), next time from 3 to 9 (which is 7). So, this is of the form I mentioned in the parentheses. Summing up the terms in the parenthesis from i=1 to i=N gives you a polynomial of the highest degree of $N^3$, since the inner loop runs N times, the order is $O(N^4)$2012-10-16
1

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.

  • 0
    No, condition might not be part of the input, it's just to show that there's a test performed I think.2012-10-16
  • 0
    @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.2012-10-16