develooper Front page | perl.beginners | Postings from February 2009

Re: How to speed up two arrays compare.

Thread Previous | Thread Next
Chas. Owens
February 11, 2009 13:53
Re: How to speed up two arrays compare.
Message ID:
On Wed, Feb 11, 2009 at 11:07, kevin liu <> wrote:
>> But this will still take O( n * m ) if all the elements of @nwarray0 are in
>> @nwarray1.
>> If the elements of @nwarray1 are sorted then you could a binary search on
>> it and reduce your worst case to O( n * log m ).
>     But how could this be, I have got the best algorithm from Rob, but I
> don't know why a binary search would be O( n * logm )
>     Could you please help to explain? Thank you in advance.

You must have n, there is no other way (which is why even using a hash
version has an amortized cost of O(n)) because you must examine all n
items in the first array.  In the naive case (searching the whole
second array) you multiply n by m because for every item in the first
array you must search m items in the second array.  Changing the naive
case to use a binary search reduces the number of elements in the
second array from m to nl m/nl 2 or as it is normally written log m.
This is because a search through the longest path through the
(balanced) binary tree is log m (so for 128 items the longest path is
7, for 256 it is 8, for 512 it is 9, etc.).

Chas. Owens
The most important skill a programmer can have is the ability to read.

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About