Follow Us :

PA of Algorithms Q91

0. Suppose P, Q, R, S, T are sorted sequences having lengths 20,24,30,35,50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is __________.

  • Option : A
  • Explanation :
    20, 24, 30, 35, 50
    Step 1 : We take

    Comparisons = (20 + 24 – 1) Max = 43
    Step 2 :

    Total comparison = 43 + (65 – 44) = 64
    Step 3 :

    Total comparison = 64 + 19 = 83
    Step 4 :

    Total comparison = 93 + 65 = 158
    = 158 + 93 + 64 + 43 = 358
Cancel reply
Cancel reply