Question

\begin{array}{1} \text { 3. Analyze the complexity of following algorithms in terms of big } \mathrm{0} \text {. [2* } 2 \text { ] }\ \begin{array}1c \hline \mathrm{i}=\mathrm{n} ; & \text { for }(\mathrm{i}=-10 ; \mathrm{i} <=\mathrm{n} / 2+3 ; \mathrm{i}++)\{ W \text { sum }=0 ; & \text { for }(\mathrm{j}=1 ; \mathrm{j}<=\mathrm{m} +3 ; \mathrm{j}++) { \text { while }(\mathrm{i}>0){ & \mathrm{a}=\mathrm{a}-10 ; \ \quad \text { for }(\mathrm{j}=\mathrm{n} ; \mathrm{j}>=\mathrm{i} ; \mathrm{j}=\mathrm{j} / 10){ & \mathrm{b}=\mathrm{b}+\mathrm{a} ; \quad \text { sum }++ & \text { sum }++; \ \quad\} & } \quad \text { i--} &\ V} & 1 \hline \end{array} \end{array} $$ CS.JG. 005

Answer 1

The complexity of the algorithm is O(n^3 * m)

Step-by-step explanation:

The complexity of the given algorithm can be analyzed as follows:

1. The outer loop runs n/2 + 14 times, which has a linear time complexity of O(n).
2. The inner loop runs m + 4 times, which also has a linear time complexity of O(m).
3. The nested while loop runs a maximum of n/10 times, which has a linear time complexity of O(n).
4. The nested for loop runs n - i + 1 times, which has a linear time complexity of O(n).

Therefore, the overall time complexity of the algorithm can be approximated as O(n * m * n * n/10), which can be simplified to O(n^3 * m).