CODEWITHSUNDEEP
data-structurestime-complexitybinary-treeheap
Vincenzo Iannucci
Vincenzo Iannucci

Reputation: 13

Check if an array is a min heap time complexity

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)?

Upvotes: 0

Views: 658

Answers (1)

Captain Giraffe
Captain Giraffe

Reputation: 14705

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).

Upvotes: 0

Related Questions