Hey Guys ,
I think using a Data structure like TRIE could also be Good solution for the question .
Just put the strings of one array into a TRIE and then search for the strings of the other array.
The Order will be 2 * O(n * d) approx
where d is the average length of all the strings in an array.
Amal.
On 7/20/06, Bruno Avila <[EMAIL PROTECTED]> wrote:
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 Avila2006/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 [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
-~----------~----~----~----~------~----~------~--~---
