3 ms·
[pedantic] Technically, look up on a balanced binary tree is still O(n) as it says nothing about the ordering. If it was a balanced binary search tree then it w
by ndr 13y ago
[pedantic]
Technically, look up on a balanced binary tree is still O(n) as it says nothing about the ordering.
If it was a balanced binary search tree then it would be O(log(n)) which I guess is the answer you gave.
[/pedantic]
A part from that I totally agree with you on the importance of knowing by heart the implications of some technical choices.
- nostrademons 13y ago(I upvoted you because you're pedantically correct, but being even more pedantic: if it's not a balanced binary search tree, is "lookup" even a valid operation on it?)
- marcosdumay 13y agoWell, lookup is a valid operation on any dataset.
- nostrademons 13y agoNot really: "lookup" is not part of the API (as taught in a typical data-structures class) for stacks, queues, and priority queues, and technically arrays/vectors let you lookup by integer but the O(N) lookup by object is only an extension that most languages provide as a convenience. If we really want to be pedantic, we'd have to define what the binary tree is used for, because there's no convention for what "lookup" means in this case. A heap, for example, can be implemented as a balanced binary tree, but the only methods it provides are push, pop, and top.
- gizmo686 13y agoThe lookup time of a binary search tree is also in O(n). Personally, regardless of the algorithm, I prefer to just say that it is in O(Ackermann(n,n)).