So it must have been the formatting for
part d, I had the same thing.
For e, where we differ, my logic was as such.
It will take O(N) to do Preorder and store the
value. It will take O(N) to do Postorder and store
he value. So total setup will take O(2N)=O(N).
Then after that if you do M queries, it takes constant
time to calulate the relative positions (since it is
already calculated), so it will take O(M).
Total time is then O(M+N).
I don't see how you get O(M*N). If it finding the relative
position of the pairs took N each query it would, but since
we do that in a preprocessing step, it will only take constant
time, hence the benefit to doing this at all. Right?
Thanks |