0

I'm having trouble understanding why this heap_maker method in python is O(N), I would assume it is O(N log N) simply because we have a nested loop, and each element may be "heaped" down comparing the current loop element to each element in the worst case scenario correct?

    def heap_maker(self, ca: ComplexArray) -> None:
    """
    Takes a complex array object in as an argument and builds
    a heap object based upon the values in the complex array
    """
    self._heap = ca #complex array can be considered like a normal python list

    #build the heap using heapify down
    n = self._heap.length() #length is O(N)
    for i in range(n // 2, -1, -1):
        j = i
        while 2 * j + 1 < n:
            left = 2 * j + 1
            right = 2 * j + 2 if 2 * j + 2 < n else left
            k = left if self._heap[left] < self._heap[right] else right
            if self._heap[j] > self._heap[k]:
                self._heap[j], self._heap[k] = self._heap[k], self._heap[j]
            else:
                break
            j = k
OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
Ransome
  • 101
  • 6
  • 2
    Who said is was linear runtime? The comment on length function is only for that line, but counting the size of any heap should ideally be constant time – OneCricketeer Mar 05 '23 at 17:32
  • You have nested loops how is it O(N)? – Talha Tayyab Mar 05 '23 at 17:33
  • 2
    Are you basing this on the comment in the code? The code only says that the `length` method is O(n), not that `heap_maker` is. – CrazyChucky Mar 05 '23 at 17:36
  • 5
    It's not specifically about *this* implementation, but [How can building a heap be O(n) time complexity?](https://stackoverflow.com/q/9755721/555045) – harold Mar 05 '23 at 17:36
  • 3
    I was also surprised to learn that heapification of an array is O(n) rather than O(n log n). The proof is not obvious. All though the worst case of the inner loop is O(log n), this doesn't actually happen. 1/2 the time it is executed once. 1/4 of the time it is executed twice, 1/8 of the time, ... So you end up with a constant average. – Frank Yellin Mar 05 '23 at 17:37
  • @GodIsOne that is what I thought, I was told that since this is using a variation of Floyd's algorithm, its somehow O(N)? – Ransome Mar 05 '23 at 17:37
  • @CrazyChucky No, the length method is a user implemented method, the comment was to just verify that the way the user is getting length is 0(N). The overall method has been told to me to be 0(N) – Ransome Mar 05 '23 at 17:39
  • @FrankYellin, I see, this is somewhat hard to conceptualize just looking at the method. – Ransome Mar 05 '23 at 17:40
  • 2
    Nested loops cannot always be analyzed by simply multiplying the number of inner iterations in the worst case by the number of outer iterations. O(n lg n) is *an* upper bound on the number of iterations, but it is not a *tight* upper bound. Loosely speaking, the inner loop is O(n) in the worst case, but o(n) in *enough* cases to reduce the overall complexity. – chepner Mar 05 '23 at 17:47
  • (Sorry, that should be the inner loop is O(lg n) in the worst case, o(lg n) in enough cases.) – chepner Mar 05 '23 at 17:56
  • 2
    Floyd's siftDown method for heapify is O(n), details why: https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap – njzk2 Mar 05 '23 at 18:02
  • 1
    I think where your analysis went wrong is in this statement: "and each element may be 'heaped' down comparing the current loop element to each element in the worst case scenario." If you examine the code closely, you'll see that the current loop element is not compared to each element. Half of the elements are never sifted down. *In the worst case* 1/2 of the remaining are moved down one level. 1/4 are moved down two levels, etc. Each move down requires two comparisons. See https://stackoverflow.com/q/49774237/56778 for additional info. – Jim Mischel Mar 08 '23 at 21:52

0 Answers0