Awesome q2a theme
0 votes
20 views
while merging two sorted array of size m,n respectively why total number of comparision is m+n-1?.

suppose

1st list  contain 2,3

2nd list containn 4,5,6

insert infinity in first list at end and infinity in second list at end.

1st  comparison of (2,4)  ----------->2 will come in Final Array

2nd comparison of (3,4) ----------->3 will come in Final Array

3rd comparison of (infinity, 4)----------->4 will come in Final Array

4th comparison of (infinity,5)----------->5 will come in Final Array

5th comparison of (infinity,6)----------->6 will come in Final Array

so according to above procedure there will be total of m+n comparision i.e here 5.
in Algorithms by (8 points) | 20 views

1 Answer

0 votes
After you insert $5$ into the result array, there is only one element ($6$) left. Why do you need another comparison to insert it ? That is where the $-1$ comes into picture.

Technically, in this example - it will take less than $m+n-1$ comparisons. After you insert $3$, left array is empty. And since right array is already sorted - you can insert into the result array directly without further comparisons.

$m+n-1$ is the upper bound.
by (1.9k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users 2020 Aug 03 - 09
  1. Mellophi

    98 Points

  2. Ashutosh777

    70 Points

  3. Kushagra गुप्ता

    12 Points

  4. srestha

    11 Points

  5. arjun12

    10 Points

  6. prakhar2810

    8 Points

  7. sdutta

    7 Points

  8. shivarajkumar

    6 Points

  9. kuldeep kumar07

    6 Points

  10. toppoavinash

    6 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Mellophi

    104 Points

  2. Ashutosh777

    73 Points

  3. Shaik Masthan

    13 Points

  4. srestha

    13 Points

  5. Kushagra गुप्ता

    12 Points

  6. arjun12

    10 Points

  7. Unnayan kumar

    8 Points

  8. prakhar2810

    8 Points

  9. sdutta

    7 Points

  10. Sourav Kar

    7 Points

7,725 questions
1,826 answers
11,148 comments
95,095 users