educative.io

Can't the time complexity be reduced to O(N)?

Courses
,
#1

The solution explains

Since we will insert all numbers in a HashMap and a Min Heap , this will take O(N*logN)O(N∗logN) where ‘N’ is the total input numbers.

But initializing a heap takes O(N). So why not initialize with all values at once?

In the end time complexity = O(N) + O(K Log K)

Right?

#2

(Examples are in JS)

Initializing a heap is not O(N) is O(N*logN).

Think of it this way. If you have a list of numbers you are adding to a heap, you’ll likely start with an array of numbers

const numbers = [1,2,3,4,5,6];

Iterating through all the numbers is O(N), correct?

Then for each iteration you have to consider the runtime cost of insertion to a heap. Which is O(logN) (Since you have to walk up the heap tree to properly place the element. So

for (const num of numbers) { // O(N)
  heap.push(num); // O(logN);
}

Because the logN is nested inside of the N, this is a O(N*logN) operation.

#3

@Gaurav7 I saw the stack overflow link you shared in your other post that talks about O(N) building of a heap. I actually didn’t know about this and will spend some time looking into it. Thanks for sharing, and ignore my comment above :sweat_smile:

For anyone else reading this: https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

#4

Initializing a heap does take O(N) (it needs an array, and has to include all elements of the array), but if we add elements to a heap one by one then it takes O(N*logN).

In the problem, we have to add elements one by one, that’s why the complexity is O(N*logN).

Even if we are able to find a solution where we could initialize the heap with ALL elements of the frequency map, we still have to add elements one by one. This is because, the heap works on an array and not on a map.

for (Map.Entry<Integer, Integer> entry : numFrequencyMap.entrySet()) {
  if (entry.getValue() == 1)
    distinctElementsCount++;
  else
    minHeap.add(entry);
}
1 Like
#6

But since we know all of the frequencies after generating frequency map, can’t we convert the hash map/dictionary into an array (O(n)) and then just heapify that array (O(n)) instead of inserting it one by one?

1 Like