Hi, I have successfully solved this problem by storing the sorted subarray at every node in my tree. But since I am calling merge function at every node, Can you tell me the time complexity it will take to build the tree.
If you need a reference to code - here it is : https://ide.codingblocks.com/s/164374 , quite easy to understand, so I haven’t documented it.
thanks!
Doubt in time complexity of buildtree function
How many node ?
2*n
How much time for that merging thing? = n
So we run in O(n^2).
But wait, the number of elements for merging at each node keeps on decreasing as we go down. So complexity is much lower than n^2.
Cant we quantify it?
Because even I thought it as O(n2) but that will not fit the time, so how will I make surity to my approach during programming contests live
Similar kind of thing is for insertion time in heap. Some integration is done and complexity is calculated. You can find it on internet.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.