which program has the better guarantee on the running time for large values of ( , ) which program has the better guarantee on the running time for small values of ( ) which program will run faster on average for , is it possible that program will run faster than program on all possible inputsa majority element in an arrayaof size is an element that appears more than / times (thusthere is at most onefor examplethe array has majority element ( )whereas the array does not if there is no majority elementyour program should indicate this here is sketch of an algorithm to solve the problemfirsta candidate majority element is found (this is the harder partthis candidate is the only element that could possibly be the majority element the second step determines if this candidate is actually the majority this is just sequential search through the array to find candidate in the arrayaform second arrayb then compare and if they are equaladd one of these to botherwise do nothing then compare and again if they are equaladd one of these to botherwise do nothing continue in this fashion until the entire array is read then recursively find candidate for bthis is the candidate for (why? how does the recursion terminateb how is the case where is odd handledc what is the running time of the algorithmd how can we avoid using an extra arraybe write program to compute the majority element the input is an by matrix of numbers that is already in memory each individual row is increasing from left to right each individual column is increasing from top to bottom give an (nworst-case algorithm that decides if number is in the matrix design efficient algorithms that take an array of positive numbers aand determinea the maximum value of [ ]+ [ ]with > the maximum value of [ ]- [ ]with > the maximum value of [ ]* [ ]with > the maximum value of [ ]/ [ ]with > why is it important to assume that integers in our computer model have fixed sizeconsider the word puzzle problem on page suppose we fix the size of the longest word to be characters