4 Algorithm analysis and correctness (35 pts) Consider the following algorithm: 1:2:3:4:5:6:7:CompleX(n)j=1a=0whilejna=a+jj=2jreturna (a) (10 pts) Determine the precise number of iterations that the while loop executes. Prove your answer using induction. Hint: Observe how the value of j changes in each iteration. (b) (5 pts) Using your answer in part (a), determine the asymptotic running time of the Complex( n ) algorithm (use notation). (c) (10 pts) Determine the value that Complex(n) returns (as a function of n ) and prove your answer using loop invariants, as presented in Chapter 2 of CLRS. Hint: Use the answer from part (a) and observe how it affects the value of a in each iteration. (d) (10 pts) Prove your answer in part (c) using induction. Observe the similarity between loop invariants and induction