1) 8 marks] Give a big-O estimate for the number of operations, where an operation is a comparison, print or a multiplication, used in these segments of algorithms Ignore comparisons used to test the conditions in the while and for loops. a) while i0) for j- 0 to n-1 print (j) n=n/2 2) [12 marks a) Find a formula for 2n by examining the values of this expression for small values of n b) Prove the formula you conjectured in part (a) 3) [I0 marks Prove that for every positive integer n, (1x2) (2x3)+(nx(n+))- (nx(n+1)x(n+2) 3 4) [10 marks Which amounts of moncy can be formed using just two-dollar bills and five-dollar bills? Prove your answer using strong induction. 5) [0 marks] Find (2(3), and f(4) if fis defined recursively by f(0)--1.fl)-2, and for n-1,2 a) f(n+1)-+3(n I) 6) [10 marks] Assume fo is the nth Fibonacci number. Prove that fi+5++-f-when e is a positive integer<>