CODEWITHSUNDEEP
arraysalgorithmsortingsearchtime-complexity
atakatom
atakatom

Reputation: 11

Developing an algorithm with O(mlogn) complexity

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.

Upvotes: 0

Views: 103

Answers (1)

btilly
btilly

Reputation: 46399

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.

Upvotes: 1

Related Questions