On 15 Apr 2014, at 12:03 pm, John Brownie <john_brow...@sil.org> wrote:
> think you're an order of magnitude out. Searching an array is linear with > the length of the array, O(n), whereas a set or hash should be close to > constant, O(1), if there's not a big collision in the hashes. But the > principle is correct, that you don't want to be searching arrays. Of course, > if it's a sorted array, you can do it in O(log n) by binary searching. Right, but you're also iterating the first list, which is O(n), so for each item you have to linear search a second list, O(n) again, so it's O(n) x O(n), or O(n^2). If the second "list" is just a hash or set, that's O(1), so overall it's O(n) x O(1) or O(n). That is, I was discussing the overall performance, not just the lookup for membership. --Graham _______________________________________________ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
