Your developing a set of algorithms for a librarian robot thatcan put newly arrived books to the main book shelf (of a sufficientcapacity) while maintaining an alphabetical order.
Design an algorithm that minimises Ccmp, the numberof comparisons of two books’ labels in the alphabetical order, andCmov, the number of book movements (one movement iscounted whenever a book is moved from one location to another) inthe worst case. Suppose there are n books on the main shelf, whichhave already been sorted in an ascending alphabetical order. The mnewly arrived books are carried into the library on a portableshelf.
a) Scenario 1: The newly arrived books have also been sorted inan ascend- ing alphabetical order and you are allowed to use atemporary shelf of an infinite capacity.
i) Design an algorithm (description + pseudo code) for the robotto arrange the new books onto the main shelf using Ccmp = Θ(n + m)label comparisons and Cmov = Θ(n + m) book movements in the worstcase.
ii) Explain why your algorithm has the stated worst casecomplexity (ignoring the constant and choosing the dominant term inyour analysis).
AlgorithmArrangingBooksScenario1(A,B,C,n,m)
//A, B, and C represent the arrays of book labels for themain, the portable, and the temporary shelves
//COMPLETE PSEUDO CODE HERE
b)Scenario 2: There is no temporary shelf to use in the libraryand the number of newly arrived books, m, is a small constantcompared to n, for instance, m = 10.
i) Design an algorithm (description + pseudo code) for the robotto arrange the new books onto the main shelf using Ccmp = Θ(log(n))label comparisons in the worst case.
ii) What is the number of book movements Cmov incurred in theworst-case of your algorithm and why?
AlgorithmArrangingBooksScenario2(A,B,n,m)
//A and B represent the arrays of book labels for the main andthe portable shelves
//PSEUDO CODE HERE
