I have 2 questions. About #8, I know the sequence is 3n-1 and I could prove it with O(3^n*n!), but I am not sure how to prove it without using the factorial. About #9, I think I could prove #10, but I could not solve multiplying with x. Could you help to solve #8 and #9? Also, could you check #10 if it makes sense?

Thanks,

(10pts) Consider the arithmetic progression {2, 5, 8, 11, ...}. Give a big-O estimate of the product of the first n numbers in the sequence without using the factorial. Note that you do not need to provide the witnesses C and k in this problem. (10pts) Determine the number of multiplications used to find x" starting with r and successively multiplying with x (to find x2, x3, x4, and so on). 10. (10pts) Determine the number of multiplications used to find x2" starting with x and successively squaring (to find x2, x4, x , and so on). Is this method more efficient than the one from the previous question?110. The squares determined from x until we found x 2 were First multiplication: x^2 Second: x^4 = x22 Third: x18 = x23 kth: (x2k-1) 2 = x2*2k-1 ~x2k-1+1 =x2k Therefore, we require k multiplications in total to determine x2". When multiplying x by itself the appropriate number of times, we require 2*multiplications to determine x2" and it is more efficient to find x2" repeatedly squaring as k