You are viewing a single comment's thread. Return to all comments →
the magic has got to do with
Collections.binarySearch()
if (pos < 0) pos = Math.abs(pos)-1
Hence, by chance in most test cases (as it seems) data.add(pos, a_i) takes O(1) as there is no shifting to be done.
data.add(pos, a_i)
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 →
the magic has got to do with
Collections.binarySearch()
which does take O(log n)if (pos < 0) pos = Math.abs(pos)-1
which for elements that are to be appended to the list, returns the last index.Hence, by chance in most test cases (as it seems)
data.add(pos, a_i)
takes O(1) as there is no shifting to be done.