QUESTION

Text
Image

# 4. (10 marks) Work out the number of elementary operations in the worst, the best and the average cases for the following algorithm (justify your answer): 00 : function Nonsense (positive integers $n$ and $m$ ) $\begin{array}{ll}\text { 01: } & i \leftarrow 1 \\ \text { 02: } & \text { while } i<n \text { do } \\ \text { 03: } & \text { for } j \leftarrow 1 \text { to } n \text { do } \\ \text { 04: } & \text { if } j \% 7=0 \text { then }\end{array}$ 05: constant number $C$ of elementary operations. 06: $\quad$ else 07: $\quad$ for $k \leftarrow 0$ to $n$ do 08: $\quad$ constant number $C$ of elementary operations. 09: $\quad i \leftarrow 5 i$ 10: $\quad k \leftarrow 5$ 11: $\quad$ while $k \leq n$ do 12: $\quad C n$ elementary operations 13: $\quad k \leftarrow k \cdot k$ 14: for $i \leftarrow 1$ to $n$ do 15: $\quad$ for $j \leftarrow 1$ to $i$ do 16: constant number $C$ of elementary operations. 17: for $i \leftarrow 1$ to $n$ do 18: $\quad$ for $j \leftarrow 1$ to $n$ do 19: $\quad C \cdot i$ of elementary operations. 20: $\quad$ return $m$  