The objective of this programming assignment is to implement in your preferred$*$ language an algorithm A to compute the sum $\_($i$=0)^$n$$ax$^$i where a and x are a real numbers $(0<=$x$<=1).$ 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$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ on different graphs. Finally, discuss your results: use the plots you will build to determine and justify the time complexity of T$($n$).($Hint: analyze ahead the time complexity T$($n$)$ of ComputeSumPowers to predict the expected shapes of $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$)))$

Algorithm A

ComputeSumPowers$($a$,$x$,$n$)$

inputs: x is a real number with $0<=$x$<=1.$ a is a real number. n is an integer $($n $>=0)$

output: a real number equal to $\_($i$=1)^$n$$ax$^$i

sum $=0$

prod $=$ x

for i $=1$ to n

sum $=$ sum $+$ prod

prod $=$ prod $*$ x

return a$*$sum a$)$

Suppose that for n very large, T$($n$)$Kg$\_1($n$)$ where K is a constant.

i$)(1$ point$)$ What would then the values of $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively? $($just replace T$($n$)$ with Kg$\_1($n$)$

and simplify the expression you get$).$

$....$ answer here

ii$)(3$ points$)$ Based on the expressions obtained in the previous question, what would then the shapes of the plots $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively?