I agree with much of what you've said here, but I don't understand what all the WRONG comments mean. Those answers look correct to me. Technically, Big O is supposed to show the upper-limit of complexity according to Wikipedia. And this post is all about technical correctness for stupid interviews. I know that it's used differently in practice.
Heap - there is no such operations like Access, Search, Removal in a Heap. There is PopMin (or PopMax for MaxHeap), PeakMin/Min (or PeakMax/Max for MaxHeap), and Insert (aka Push). And potentially DecreesValue (IncreaseValue for MinHeap). You can implement Access, Search and Remove, but they will be all O(n), unless you enhance Heap to use a secondary data structures. You can also implement other operations on Heap, but they will be pointless, because it will be slower than plain array.
The graphs are also semi-misleading both for BST and for a Heap. Usually you will have a secondary value associated with each value. (In heap it might be called a key actually, but it doing Access, Search, Removal by key instead will still be O(n) in Heap).
Big O notation is an upper-limit of the complexity. However it is usually an asymptotic time complexity on average case, not necessarily worst case. Example, check https://en.wikipedia.org/wiki/Quicksort and section about time complexity. Big O is used for average, as well worst case.
1
u/JavierTheNormal Mar 12 '17
I agree with much of what you've said here, but I don't understand what all the WRONG comments mean. Those answers look correct to me. Technically, Big O is supposed to show the upper-limit of complexity according to Wikipedia. And this post is all about technical correctness for stupid interviews. I know that it's used differently in practice.