Question

By concentrating on the dominating step(s) and also assuming that all basic operations are having the same constant cost C, compute Tworst-case(n) in closed-form for the following program segment. Do not simplify your solution. Remark: You must first set up the summation equation for Tworst-case(n) and then evaluate the sums. x = 168; y-268; for i-1 to n do for J-to n do y=x-y; for k-1 to i do y = x*y/210 endfer endfor endfer

Please explain your thought process as your complete this problem

Answer 1

The k loop runs i times for each j

The j loop runs from i to n for each i

The i loop runs n times from 1 to n

So total number of steps is (removing all constant multiples)

7l 7t

This is $\sum_{i=1}^{n}\sum_{j=i}^{n}i$

Which equals $\sum_{i=1}^{n}(n-i+1)i$

That is,

(n + 1)Σ_Σ2

That is, $(n+1)\frac{n(n+1)}{2} -\frac{n(n+1)(2n+1)}{6}$

This equals ${\color{Red} \frac{n(n+1)(n+2)}{6}}$

The worst case complexity is therefore

Θ(n3) 7l

$\blacksquare$

Please do rate this answer positively if you found it helpful. Thanks and have a good day!