[algogeeks] Re: Which is the fastest solution for comparing two arrays?

Wed, 19 Jul 2006 17:00:20 -0700

To sort an array A you could use Radix Sort, which complexity is O(d*n), where d = log2(max(A)). So,

sort the first array -> O(d*n)
sort the second array -> O(e*n)
compare the two arrays -> O(n)
the solution : (d+e+1)*O(n) = O(n)

Use it only if (d+e+1) is smaller than the hash constant.

Bruno Avila

2006/7/19, ridvansg <[EMAIL PROTECTED]>:

L7,
from the first array make a hash table H-> O(n)

go through the second array and test if the element is present in H1
->O(n)

so the solution is 2*O(n)=O(n)

Your solution:
sort the first array -> O(n log n)

sort the second array -> O( n log n)

compare the two arrays -> O(n)

the solution : 2*O(n log n) + O(n) = O( n log n)


Siva how will you use the B-tree, so you can make one node to
correspond to one block in the disk but how will you contro the writing
the each node to the disk. This is a issue of low level programing for
me. Siva please explain?



--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to