0

I am struggling to find the exact solution for this question.

A university has two student clubs. The number of students registered to the first club is m and their IDs are stored in an array A (with m elements) whereas the number of students registered to the second club is n and their IDs are stored in an array B (with n elements), where m≤n. A student might be registered to either one of these clubs or both. We want to decide how many students are registered to both clubs. Given two arrays A and B along with their lenghts m and n, write a O(mlogn) algorithm (as a pseudocode) to find the number of elements that are registered to both clubs. For example, when A is [2, 6, 3, 9, 11, 8] and B is [3, 11, 7, 4, 2, 5, 1], the algorithm must return 3 corresponding to the students with IDs 2, 3 and 11.Explain why your running time is O(mlogn) in sufficient detail.

First thing that comes to my mind is sorting the array B and then searching match for each element in B from A. Sorting O(nlogn), looking for match O(mlogn) then the conluded result becomes O((m+n)logn).

Second way on my mind was to merge the arrays then look for the duplicates but idk.

atakatom
  • 11
  • 3
  • *"Inside your pseudocode, you are allowed to use functions that are already defined in class videos, slides and book."* Looks like you are way ahead of us! We didn't follow that class :( – Stef Dec 28 '21 at 18:22
  • If you need a solution that works out of the box, you can try to take a look for example here: https://stackoverflow.com/questions/2864842/common-elements-comparison-between-2-lists If you want to understand how does it work then you have to read your book. – IgorZ Dec 28 '21 at 18:26
  • 1
    `n` could be much bigger than `m logn`, and you have to examine all elements of `B`. So, I can't see how it is possible...are you allowed to use hashing? – Damien Dec 28 '21 at 18:26
  • Are you sure they want you to do it in m log(n) and not n log(m) ? That would be much easier – Stef Dec 28 '21 at 18:27
  • 1
    Also can you assume that the arrays are already sorted? In that case it could be done in m log(n) easily. – Stef Dec 28 '21 at 18:29
  • Well we are having the hardest time in class because of these kind of questions :( – atakatom Dec 28 '21 at 20:05

1 Answers1

1

There is something wrong with the question.

If B starts sorted, there is a O(m log(n)) algorithm.

If neither is sorted, there is a O(n log(m)) algorithm.

But if neither is sorted, you cannot even search B once without taking time O(n). And O(m log(n)) needs to run faster than that in the limit where m goes to infinity while n = m^2.

btilly
  • 43,296
  • 3
  • 59
  • 88