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 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
    @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