A bank has issued two separate sets of account access cards, set A and set B. Ea

Question

A bank has issued two separate sets of account access cards, set A and set B. Each set consists of n

cards and for every card in the set A there is a corresponding card in the set B that belong to the same account, and we will refer to these two cards as the matching pair. Each card is a small plastic object containing a magnetic strip with some encrypted number that corresponds to a unique account in the bank. It is required to find all matching pairs. There is a card reader machine such that when two cards

, one from set A and one from set B, are inserted in the machine one of its three light indicators turns on; green if the pair matches, red if the account number on A is larger than B, and yellow if the number on B is higher than that of A. However, the card reader cannot

compare two cards belonging to the same set.

(a)Describe an algorithm in clearly defined step that uses (n^2)tests to find the

matching pairs.

(b)Describe a more efficient algorithm with an average case

complexity of O(n lg n) tests to find the matching pairs. Prove that your algorithm satisfies the

desired complexity.

Explanation / Answer

Consider the following algorithm.

Eventually you will get a time complexity like O(n) + 2* O(n / 2) + 2* O(n / 4) + 2* O(n / 8) etc.. Breaking down the problem like this using a binary search tree on every correct pairing, I believe the time complexity will be O(n log n). In the worst case it will obviously be O(n^2) just like quicksort.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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