Revision as of 22:18, 20 November 2014 edit 2a01:e35:2f45:9a0:ba76:3fff:fef7:e4d5 (talk) →hash table are not in O(1): new section ← Previous edit		Revision as of 23:21, 20 November 2014 edit undo Intgr (talk \| contribs) Autopatrolled, Extended confirmed users, New page reviewers, Pending changes reviewers 32,266 edits →hash table are not in O(1): reply Next edit →
Line 64: Thus, search is O(log(n)) in both case. [[Special:Contributions/2A01:E35:2F45:9A0:BA76:3FFF:FEF7:E4D5\|2A01:E35:2F45:9A0:BA76:3FFF:FEF7:E4D5]] ([[User talk:2A01:E35:2F45:9A0:BA76:3FFF:FEF7:E4D5\|talk]]) 22:18, 20 November 2014 (UTC) :Er, what? :> ''the assumption that the cost of calculating a hash and performing a comparison is comparable asymptotically, which is not the case when n goes to infinity'' :The complexity of calculating the hash is assumed to be constant, just like greater/less comparisons in a tree lookup aren't factored into the O() complexity. That's a fair assumption given constant-length keys. :> ''Indeed, if you have a set of n elements, you need at least log(n) bits to represent them'' :This applies just as well to a binary tree structure that needs to store left/right pointers, pointer size needs to be at least log(n). So by your argument its complexity should be O(log(log n))? :-- [[user:intgr\|intgr]] <small>[[user talk:intgr\|[talk]]]</small> 23:21, 20 November 2014 (UTC)

Talk:Self-balancing binary search tree: Difference between revisions