You are viewing a single comment's thread. Return to all comments →
complexity will be O(log(n)) for below line of code:
int pos = Collections.binarySearch(data, a_i);
complexity will be O(n) for below line of code (for shifting elements to right):
data.add(pos, a_i);
So total complexity = O(log(n)+n) = O(n).
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 →
complexity will be O(log(n)) for below line of code:
complexity will be O(n) for below line of code (for shifting elements to right):
So total complexity = O(log(n)+n) = O(n).