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 a binary search taking O(log n) followed by array insertion taking O(n) followed by an array lookup taking O(1) for n items. So the complexity is O(n (log n + n + 1)) or O(n^2). That is slower than the heap-based O(n 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 a binary search taking O(log n) followed by array insertion taking O(n) followed by an array lookup taking O(1) for n items. So the complexity is O(n (log n + n + 1)) or O(n^2). That is slower than the heap-based O(n log n).