I was given a question that is stated that;
Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection of n bank cards that they’ve confiscated, suspecting them of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Each account can have many bank cards corresponding to it, and we’ll say that two bank cards are equivalent if they correspond to the same account. It’s very difficult to read the account number of a bank card directly, but the bank has 1 a high-tech ‘equivalence tester’ that takes two bank cards and, after performing some computations, determines whether they are equivalent. Their question is the following: among the collection of n cards, is there a set of more than n/2 of them that are all equivalent to one another? Assume that the only feasible operations you can do with the cards are to pick two of them and plug them into the equivalence tester. Show how to decide the answer to their question with only O(nlog n) invocations of the equivalence tester.
I proposed an algo for this problem that is like this;
For the equivalent majority there must be majority of the equivalent cards on one side of the n cards if we divide them into two halves. So one of the two sides must return one card that has majority more than n/2 in whole list.
Let’s say equivalentTest is the function that takes two bank cards and, after performing some computations, determines whether they are equivalent.
Function checkMajority(c, M) i = count = 0 While i less than length of M: if (M[i] is not actual c) and (equivalentTest(M[i], c) == true) then: count ++ Endif Endwhil If count is greater than half the length of M then: Return true Else Return false Endif Function divide_and_find(M) If M.length = 1 Return M Else if M.length = 2 If equivalentTest(M, M) == true Return M or M Divide M M1 = assign first half M2 = assign second half c = divide_and_find(M1) if c is returned then found = checkMajority(c, M) If found = true then Return c Else c = divide_and_find(M2) found = checkMajority(c, M) If found = true then Return c Else Return ‘not found’ Endif Endif Endif Return ‘not found’
According to my understanding,
The algorithm complexity is O(nlogn) because we have used divide and conquer strategy. There would be (logn) steps and each step would take O(n) time for checking the majority. So the complexity would be O(nlogn)
But at the same time, I think it will take O(n*n).. that is big O of n square, In worst case scenario. Because then it will check n cards for n cards, to find duplicate cards.
Can any one help me out in resolving my confusion??