Consider the following algorithm: 1: COMPLEX (n) 2: j = 1 3: a - 0 4:...

Transcribed Image Text:

Consider the following algorithm: 1: COMPLEX (n) 2: j = 1 3: a - 0 4: 5: 6: 7: while j<n a = a + j j= 2.j return a (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. Consider the following algorithm: 1: COMPLEX (n) 2: j = 1 3: a - 0 4: 5: 6: 7: while j<n a = a + j j= 2.j return a (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.

Answer rating: 100% (QA)

a To determine the number of iterations lets observe how the value of j changes Initially j 1 and in ... View the full answer