Objective:

The objective of this programming assignment is to implement in your preferred* language an algorithm A to compute the sum i=1nxi where x is a real number (0x1 ). We are interested in exploring the relationship between the time complexity and the real time (wall time). For this exploration, you will collect the execution time T(n) of Algorithm A as a function of n and plot T(n)n , T(n)n2, , and T(n)ln(n) on different graphs.

a) Suppose that for n very large, T(n)Kn where K is a constant.

i) (0.5 point) What would then the values of T(n), T(n)², and T(n)/ln(n) be, respectively? .... answer here

ii) (1.5 points) What would then the shapes of the plots T(n), T(n)², and T(n)/ln(n) be, respectively? .... answer here(NEED PLOT)

b) Suppose that for n very large, T(n)Kn2 where K is a constant.

i) (0.5 point) What would then the values of T(n), T(n)², and T(n)/ln(n) be, respectively? .... answer here

ii) (1.5 points) What would then the shapes of the plots T(n), T(n)², and T(n)/ln(n) be, respectively? .... answer here (NEED PLOT)

c) Suppose that for n very large, T(n)Kln(n) where K is a constant.

i) (0.5 point) What would then the values of T(n), T(n)², and T(n)/ln(n) be, respectively? .... answer here

ii) (1.5 points) What would then the shapes of the plots T(n), T(n)², and T(n)/ln(n) be, respectively? .... answer here(NEED PLOT)

sum Algorithm A ComputeSumPowers (x, n) inputs: x is a real number with 0 1) output: a real number equal to 1=1 xi 0 for i = 1 to n prod = = 1 for j = 1 to i prod prod * x sum +prod return sum sum = sum Algorithm A ComputeSumPowers (x, n) inputs: x is a real number with 0 1) output: a real number equal to 1=1 xi 0 for i = 1 to n prod = = 1 for j = 1 to i prod prod * x sum +prod return sum sum =