For the following algorithm, the function base() is to be considered the basic operation. The size of the input is given by n. Perform a worst-case analysis:
for(i = 0; i < n; i++)
for(j = 0; j <= n; j++)
for(k = i; k <= i*i; k++)
if(condition(i,j,k))
b[i][k] = base(b[i][j])
else
b[i][k] = b[j][k]
Could anyone guide me through solving this? I'm new to this topic and struggling to find a coherant example online.
The condition here is immaterial. In any case, the triple loop will be executed as follows.
The outermost $i$ loop will be executed $n$ times The next one $j$ loop will be executed $(n+1)$ times
The inner $k$ loop is the interesting. The $i$th time it is executed $(i^2 - i + 1$) times. (Take the case when, say $i = 3$, it will be executed for $k = 3,4,5,6,7,8,9$.
So the total executions of the inner loop are $$\sum_{i=0}^{n-1} (i^2 - i + 1) = \sum_{i=1}^{n} (i^2 - 3i + 3)= \frac{(n^2+n)(2n+1)}{6} - 3\frac{(n)(n+1)}{2} + 3n\tag{...for inner loop}$$
The final answer is in simplifying this and multiplying with the $n(n+1)$ iterations for the 2 outer loops.