-Write theBinary Search algorithm in pseudocode. Analyzethe algorithm for time needed as the size n of the problem changes.
-write Ternary Search an algorithm where instead of dividing the sortedarray into two parts, we search by dividing the relevant part of the array into three parts,determine which part the item we are looking for appears, and recursively search for the itemin this part. Write this algorithm in pseudocode. Analyze the algorithm for time needed asa function of the size n of the problem.
-Implement the two algorithms. First, generate sorted arrays of random numbers of increasinglength from 0 to 100,000 in steps of 5,000 (i.e., the first array has 0 elements, the 2nd has 5,000elements, the 3rd has 10,000 elements, and so on). Let each random number you generate bebetween 0 and 100,000. Then, perform the two algorithms on each of the generated arrays,searching for randomly generated numbers on each of the arrays. Keep track of the amountof time required to search for randomly generated numbers as a function of the lengths of the arrays.
You need to compare how the theoretical analysis compares with the time taken in practiceby the two search algorithms. To do this, draw graphs based on your experiments. On theX-axis, you will have the size of the problem and on the Y-axis, you will have the time takenfor searching. Scale the graphs appropriately so everything fits nicely on your [login to view URL] label your graphs; if I can’t tell what each of your plots is supposed to mean, I can’ttell if you did the work correctly. Use a computer graphing tool. Don’t graph by hand! Howdo your experimental results compare with the theoretical results? You must show this interms of the graphs you obtain from experiments. One way to do this is to use some program(Microsoft Excel, for instance) to fit a curve to the points you obtain experimentally. Theprogram should give you an equation for the curve. Compare the curve with the function youobtain theoretically. They should be similar if everything works out, in terms of Θ [login to view URL] there is a discrepancy between the theory and experiment, try to explain what might becausing it.
7 freelancers are bidding on average $33 for this job
Hello, I'm an IT engineer with a master degree. I've got 3 years of professional experience in C/C++. I can do your work. Contact me if you are interested. Regards, Kim