Perl Monk, Perl Meditation  
PerlMonks 
Re^3: Patience Sorting To Find Longest Increasing Subsequenceby demerphq (Chancellor) 
on May 06, 2006 at 09:02 UTC ( #547804=note: print w/replies, xml )  Need Help?? 
A merge sort is only O(N^2) worst case so no, No, a merge sort is worst case O(n log n). You are welcome to use a Van_Emde_Boas_tree which claims to be able to do the whole thing in O(N Log N) Actually the paper by Bespamyatnikh & Segal contains a proof that you can do it in O(N log log N) time. I havent verified it tho. But I doubt that the vEB based algorithm would in practice beat a simpler algorithm to do patience sorting. Unless I guess if you were dealing with a deck with tens of thousands or even millions or billions of cards. The overhead of maintaining a vEB tree is prohibitive for small datasets. The cost of doing binary operations on the keys, maintaining the vEB tree and etc, would most likely outweigh that of a simpler less efficient algorithm. As bart said, sometimes a binary search algorithm is not as fast a scan, even though one is O(log N) and the other is O(N). The reason of course is that bigoh notation glosses over issues like cost per operation, and only focuses on the "overwhelming factor" involved. So in a binary search if it takes 4 units of work to perform an operation and in linear search it takes 1 then binary search only wins when 4 * log N < N, so for lists shorter than 13 elements there would be no win to a binary search. And I'd bet that in fact the ratio is probably something like 20:1 and not 4:1. Apply this kind of logic to a deck of 52 cards, and IMO its pretty clear that vEB trees are not the way to go for this, regardless of the proof.
 $world=~s/war/peace/g
In Section
Meditations

