Re:The Problems with Live Coding Interviews
by Freire_Herval on Tuesday April 25, 2023 @09:27PM
(#35708782)
There's an error in my calculations. Apologies.
The comparison happens at every level and NOT every node so, it's O(N) for traversal then when a layer is completed a comparison occurs at a cost of O(N^2). The amount of times this happens is equal to the height of the tree which can be simplified to logN. So total big O is O(N) + O(N^2 * log2(N)).
This simplifies to O(N^2 * log2(N)) which, while better than O(N^3), is still really bad.
The comparison happens at every level and NOT every node so, it's O(N) for traversal then when a layer is completed a comparison occurs at a cost of O(N^2). The amount of times this happens is equal to the height of the tree which can be simplified to logN. So total big O is O(N) + O(N^2 * log2(N)).
This simplifies to O(N^2 * log2(N)) which, while better than O(N^3), is still really bad.