- consider the following "justificationthat the fibonacci functionf( (see proposition is ( )base case ( < ) ( and ( induction step ( )assume claim true for consider (nf( ( by inductionf( is ( and ( is ( thenf(nis (( ( ))by the identity presented in exercise - thereforef(nis (nwhat is wrong with this "justification" - consider the fibonacci functionf( (see proposition show by induction that (nis (( / ) - let (xbe polynomial of degree nthat isp(xni= ai xi (adescribe simple ( )-time algorithm for computing ( (bdescribe an ( log )-time algorithm for computing ( )based upon more efficient calculation of xi (cnow consider rewriting of (xas (xa ( ( ( (an- xan )))which is known as horner' method using the big-oh notationcharacterize the number of arithmetic operations this method executes - show that the summation ni= log is ( log nc- show that the summation ni= log is ( log nc- an evil king has bottles of wineand spy has just poisoned one of them unfortunatelythey do not know which one it is the poison is very deadlyjust one drop diluted even billion to one will still kill even soit takes full month for the poison to take effect design scheme for determining exactly which one of the wine bottles was poisoned in just one month' time while expending (log ntaste testers - sequence contains integers taken from the interval [ ]with repetitions allowed describe an efficient algorithm for determining an integer value that occurs the most often in what is the running time of your algorithmprojects - perform an experimental analysis of the three algorithms prefix average prefix average and prefix average from section visualize their running times as function of the input size with log-log chart - perform an experimental analysis that compares the relative running times of the functions shown in code fragment