( n cards are there initially )
we pick out the first card in random it takes n-1 comparisons to figure out
its Equivalence card - n-1 steps
Two cards have been eliminated ( this leaves us with 2 and n-2 cards)
we pick out the 2nd card in random it takes n-3 comparisons to figure out
its Equivalence card - n-3 steps
we continue to do this.. till all cards are exhausted ( leaves us with 2
and n-4 cards again)
the last comparison will
have
- n-(n-3)
the sum of all these steps - (n-1) + (n-3) + (n-5) + .........+
(n-(n-3))
if you draw this in the form of a tree.
n - n
2
n-2 - n
2
n-4 - n-2
2
n-6 - n-4
2
n-8 - n- 6
the height of the tree will be log n , sum @ each level is atmost n
so Big oh(n log n)
On Wed, Apr 1, 2009 at 10:53 AM, hanumant <[email protected]> wrote:
>
> Suppose you are 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 off a bank card
> directly, but the bank has 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 in to the
> equivalence tester. Show how to decide the answer to their questions
> with only O(n log n)
> invocations of the equivalence tester.
>
>
> Also can someone point me to where i can get additional problems?
>
> Thanks
>
>
> >
>
--
With technolove
DragonZsnakE
a.k.a
Prabhu hari.D
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
