3. Determine the number of comparisons (as a function of n and m) that are perfo

Question

3. Determine the number of comparisons (as a function of n and m) that are performed

in merging two ordered files a and b of sizes n and m, respectively, by the merge

method presented in the lecture, on each of the following sets of ordered files:

a. m=n and a[i] < b[i] < a[i+1]

b. m=n and a[n] < b[1]

a[i] refers the value in position i of file a, etc.

4. Determine the number of comparisons (as a function of n and m) that are performed

in merging two ordered files a and b of sizes n and m, respectively, by the merge

method presented in the lecture, on each of the following sets of ordered files:

a. m=n and a[n/2] < b[1] < b[m] < a[(n/2)+1]

b. m=1 and b[1] < a[1]

c. m=1 and a[n] < b[1]

a[i] refers the value in position i of file a, etc.

For questions 5 – 8, compare the efficiency of searching an ordered sequential table of size n

and searching an unordered table of the same size for the key key:

5. If no record with key key is present

6. If one record with key key is present and only one is sought.

7. If more than one record with key key is present and it is desired to find only the first

8. If more than one record with key key is present and it is desired to find them all.

Explanation / Answer

3. Given two disjoint lists, say we will call them N1 and N2 (whose combined number of elements is N, and where the sizes of the respective lists are n and m such that N = n+m and 1 <= n,m <= N-1), assuming each possible ordered list is just as likely as any other ordered list, it is shown that the average number of comparisons to merge N1 and N2 into one ordered list is approximately N - 2.therefore in both the cases it will be , same .

4.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.