0

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.

Xian
  • 89
  • Worst case analysis would mean the maximum iterations of this triple loop. Clearly $i$ will go $n$ times. What about $j$ and $k$ – Shailesh Oct 10 '15 at 23:41
  • j will go n+1 times and k will go i^2 - i + 1 times I believe, might be wrong though. the if(condition) else () confuses me; what if the condition is never true? Our prof. doesn't teach us any material related to the things he assigns, and the TA's struggle horribly to answer questions. Thanks for the -1 though, whoever did that. – Xian Oct 10 '15 at 23:48
  • 1
    Welcome Math.SE! Take the tour to get familiar with this site. Mathematical expressions and equations can be formatted using $LaTeX$ syntax. Guidelines for homework questions, please share your thoughts and attempts towards the solution. If you receive useful answers, consider accepting one. – Shailesh Oct 11 '15 at 00:18

1 Answers1

0

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.

Shailesh
  • 3,789
  • 1
    does: $\sum_{i=1}^{n} (i^2 - 3i + 3)$ assume that you already did the n+1 (j loop)? I understand $i^2 - i + 1$ being multiplied by $\sum_{j=0}^{n+1}$, and then $\sum_{i=0}^{n}$ – Xian Oct 11 '15 at 21:30
  • 1
    would it be safe to assume the worst-case runtime is $\theta{(n^4)}$? – Xian Oct 11 '15 at 22:10
  • The last term is order $n^3$ so finally it will be order $n^5$ – Shailesh Oct 11 '15 at 23:43
  • Am I correct when saying the worst case and the best case are of order $n^5$, thus being able to describe the algorithm as being big theta of $n^5$? Thanks for all the help also, much appreciated. – Xian Oct 12 '15 at 22:20
  • @Xian. Yes. Absolutely. – Shailesh Oct 12 '15 at 23:26
  • From looking at it, it looks like $n^4$ order, however is it $n^5$ because we have $(n^2 + n)(2n + 1)$ in the first term (order $n^3$), then we need to multiply by n and n + 1, which would raise its order another two times, going to $n^5$? – Xian Oct 13 '15 at 01:21
  • @xian. Yes. That's how it is done – Shailesh Oct 13 '15 at 01:37
  • 1
    turns out your answer was incorrect, it it $n^4$, as I thought in the previous comment. -1. – Xian Oct 23 '15 at 05:28
  • @Xian. I will certainly take a look at it – Shailesh Oct 23 '15 at 05:51