Check if an array is a min heap time complexity

Question

I implemented a recursive algorithm to check if an array is a min-heap. I can't figure out what the worst case time complexity should be. Here's the code:

CHECK-MIN-HEAP(A, i, n)
    if i > (n - 1) / 2
        return true
    if A[i] > A[left(i)] or A[i] > A[right(i)]
        return false
    return CHECK-MIN-HEAP(A, left(i), n) and CHECK-MIN-HEAP(A, right(i), n)

A brief explanation: the base case is represented by the case in which a node is a leaf. This because the element A[(n-1)/2] represent the last not-leaf node. The other base case is when the min-heap condition is violated. In the recursive case we check if the left and right subtrees are heaps.

So in best case, when the array isn't an heap, we have a constant time complexity. In the worst one, when the array is an heap, the function check all the nodes of the heap and 'cause the height of the heap is logn, the time complexity should be O(logn). Is correct? Or the time complexity is O(n)?

Each element is visited once, so O(N) seems to be the obvious call here, unless left(i) or right(i) does something really odd. — Captain Giraffe
This algorithm may be wrong. Because A[right(i)] may not always exist in the check A[i] > A[right(i)]. Consider the heap 1, 2, 3, 4. In this heap, 2 has a left-child (4) but no right-child. — Cem

Captain Giraffe Captain Giraffe · Accepted Answer · 2021-01-20T21:33:48

O(N) is obviously the correct answer here.

It is obvious because you traverse the entire array element by element looking for invalid invariants.

The best case you state is quite useless as an analysis point, it might be that the final node is invalidating the entire heap O(N).

Check if an array is a min heap time complexity

1 Answers