Note: You should NOT use any actual programming code (in C++, Java, etc) to answer the questions. If you do so, you will get only a ZERO for the question.

Question 9 (15 points) Develop a time and space-efficient iterative algorithm to determine the sum of the following series (for inputs X and n ): S(X,n)=1+X+X2+X3++Xn such that the number of multiplications encountered is a linear function of ' n ' (i.e., of the order of ' n '). (i) Write a pseudo code for the iterative algorithm you come up with. (ii) Determine the basic operation of your algorithm. (iii) Is there a best case different from worst case or the best case is same as the worst case? Justify your answer with an explanation as well as an example. (iv) Depending on your answer for (iii), determine the best case as well as the worst case (if the best case is different from worst case) or just the number of times (if the best case is the same as the worst case) the basic operation is executed as a function of the input size ' n '. Justify your answer. (v) Is your algorithm in-place or not with respect to space complexity? Justify your answer. Note: You will get a ZERO for the question if you provide a recursive algorithm as your solution