Reference no: EM132337010

Question

Consider the following function:

int mystery3(int

n)

{

int s = 0;

for (int i=1; i<=n; i++)

{

int ci = 0;

for (int j=1; j<=i; j++)

{

ci+=1;

}

s += ci;

}

return s;

}

i) Indicate the total running time of the algorithm using O-notation (function class). Clearly show your work. You do not need to calculate the exact number of steps but clearly indicate how you arrived at the answer.

ii) Create an English statement to describe what the function does-hint, try running the program in the terminal.

iii) Can this function be improved with respect to its big-O running time? If so, write down the improved function(in pseudo-code or in proper C code). If not, clearly indicate why it cannot be improved (you may use an English explanation -no formal proof necessary)