13 Nov
2003
13 Nov
'03
1:38 p.m.
Stefan wrote: [snip]
Isn't it O(min(m,n))? You don't have to look at all elements for the intersection. Eg:
{0,1,10} {0,3,98,183,398,1038,5319,7642,9811,13893,93123}
O(f) describes the worst case of the algorithm. It is O((m,n)->m+n). The average cost may be lower, but it depends on the distribution of the data.
Yes, and maybe these input lists make it a bit clearer: A = {0, 5, 10} B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Kind of hard to just "jump over" the B-exclusive elements... /David