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.

Improve this question
6
  • "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 :( Commented Dec 28, 2021 at 18:22
  • If you need a solution that works out of the box, you can try to take a look for example here: stackoverflow.com/questions/2864842/… If you want to understand how does it work then you have to read your book. Commented Dec 28, 2021 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? Commented Dec 28, 2021 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 Commented Dec 28, 2021 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. Commented Dec 28, 2021 at 18:29

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

How does it become O(n log(m)) if neither is sorted?
@atakatom Because (n+m) log(m) = O(n log(m)) since m = O(n)
@atakatom Sort A, do a binary search of A for each element of B. Worst case O(n log(m)). If you hash A instead you'll get an average case of O(n).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.