0% completed
Space and time complexity analysis not correct for python
Lee
Feb 21, 2024
Heapq.heapify(some array) is O(n) in python. So the total time complexity is O[n + k * log(n) + n]. I'm not sure what the analysis of largest component here is, so I would just call this O(n + k*log(n)).
For space complexity, because they python heapq library operates on the provided gifts list in place, there is no additional space allocated for a new heap array. Thus the space complexity should be O(1).
3
0
Comments
Design Gurusa year ago
For space complexity, we have created a new array and then used it for the heap. That is why the space complexity is O(n). Here is the line where we create a new array:
max_heap = [-gift for gift in gifts]
Design Gurusa year ago
The time complexity of heapq.heapify(max_heap) in Python is O(n). For Java since we are using all elements one by one that is why it is O(n log n).
On this page