(a) Consider the code below and invariant that follows then answer the questions that follow: 1. k = 0 2. for i=0 to n 3. k = k + 21 Loop Invariant: Before the start of the ith iteration, k = 2 - 1 i. (3 points) What does the code above do? ii. iii. (10 points) Show the invariant is true at initialization, maintenance and termination of the loop. Then use that fact to prove the correctness of the loop (7 points) For each line of pseudocode above, show next to the line a cost ci for the cost of the line, and an expression for the number of times that line is executed. Based on this, give a formula for the run time T(n) of the function. Based on this cost, estimate a e-bound for T(n).