Question: please answer all I am very confused thanks Exercise 2 (60 points) Analyze A Silly Algorithm 1. Consider the problem to compute the sum =

please answer all I am very confused thanks
Exercise 2 (60 points) Analyze A Silly Algorithm 1. Consider the problem to compute the sum = ax' where x and x are real numbers with OSXs 1. Below is a silly (naive and inefficient) algorithm A to compute the sum =o ax'. ComputeSumPowers (mm) inputs: x is a real number with 0 SX S1. a is a real number. n is an integer (n = 1) output: a real number equal to = ax! 1: sum = 0 2: for i = 0 ton 3: prod = 1 4: for j = 1 to i prod prod sum +prod 7: return sum All the questions in this exercise are related to the computeSumPowers (a,xn) algorithm. The objective of this exercise is to explore whether the asymptotic time complexity will change if we count different "actions". 5: a 6: Sum A) (20 points) Comparison Action (Lines 2 and 4). In this case, we count the total number of comparisons performed by the "for loops statements (Lines 2 and 4). Answer the following questions to determine the total number of comparisons performed by the algorithm. a. (1 point) How many comparisons in total are performed by the "for loop" statement in Line 2 during the execution of the algorithm? b. (12 points) Let us call t the number of comparisons performed by the "for loop" in Line 4 for a given value of i. Fill in this table Justify how you find t only for i= 1 and i=n): ti 1 2 3 k n c. (1 point) Based on b., express the total number of comparisons performed by the "for loop" in Line 4 only during the execution of the algorithm. d. (5 points) Express the function fe(n) that represents the overall total number of comparisons performed by the "for loops" statements in Lines 2 and 4 during the execution of the algorithm. e. (1 point) The function fe(n) grows like
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
