We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is only correct if we are always appending to the arraylist, which is not the case here. Using the indexed insertion in an arraylist is a linear time O(n) operation, since we must shift all of the subsequent elements down the arraylist. With the binary search for the index being a O (log n) solution, this gives us a final time complexity of O(n^2 log n).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
This is only correct if we are always appending to the arraylist, which is not the case here. Using the indexed insertion in an arraylist is a linear time
O(n)
operation, since we must shift all of the subsequent elements down the arraylist. With the binary search for the index being aO (log n)
solution, this gives us a final time complexity ofO(n^2 log n)
.