Big O for this recursive algorithm

Question

I did the following algorithm involving a Binary Heap structure:

Algorithm: heapMinimum(node)
Input    : Position n
Output   : Sequence minList; containing the postions that hold the minimum value

1. minList <-- sequence
2. if parent(node) == NULL // current node is the root of the tree
3.   minList.insertLast(node)
4. if (leftchild(node).element() == node.element())
5.   concat(heapMinimum(leftchild(node), minList))
6. if(right(node).element() == node.element())
7.   concat(heapMinimum(rightChild(node), minList))
8. return minList

What the algorithm does is basically traverse a Binary Heap given its root to find and store the nodes that hold the minimum value (ie the value that matches that of the root).

Now I'm having trouble calculating the running time, in Big O notation, of my algorithm. The reason I'm getting confused is because of the recursion that is used to traverse the left and right children of each node.

All of the operations run in constant time, O(1), except concat. But how do I exactly go about in calculating the running time of such a recursive solution ?

Answer 1

Looks like O(N) to me, where N is the number of elements. If your heap contains nothing but equal elements, all the elements will be traversed. Also, why isn't concat O(1)? As long as you are "concatenating" numbers, it should also be O(1). If somehow concat is O(N) however (from your pseudocode it looks like it is - but you should reconsider if you really need to concatenate the two returned lists), then the total time would be O(N²) worst case.

Answer 2

I assume you are talking about a binary heap?

By definition of the heap properties, you should only be recursing until you find an element larger than what the root is. However, you must also be certain that none of the other elements at the current level of the tree are the same size as the root. Essentially, this yields the rule that once you encounter an element of the heap that is greater than the root, you do not need to recurse into the element's children.

However, in the worst case, each element may be equal to the root. In this case, you must check the entire heap, which yields O(n) time, where n is the number of elements in the heap.

So to answer your question, it is O(n)

Answer 3

As others have mentioned, if your concat() is O(1) [and if it's not, you can make it so] then your algorithm is O(N) in the size of the output.

However, if you used a concat() that copies your list (depending on the system, this can be easy to accidentally do), then your worst case is O(N^2) in the size of the output. A case that causes this behavior is when your minimum nodes go deep into the tree, such that your concat() keeps copying the list at each level.

Note that this depth is bounded by the depth of your heap, so if your tree is balanced, this worst case is also O(M log M) in the size of the datastructure. You can see this because the maximum number of copies is the depth of the tree.

Answer 4

I suppose you have a bug in your solution. The first check:

if parent(node) == NULL

must be removed, but the check that node != NULL must be added.

Moreover, I suggest to use list as additional parameter, where you will put the answer. So, that is my implementation:

Algorithm: heapMinimum(node, minList)
if (node != NULL)
{
   if (minList.empty() || minList.getFirst().element() == node.element())
   {
      minList.insertLast(node)

      heapMinimum(left(node),  minList)
      heapMinimum(right(node), minList)
   }
}

Assuming that adding an element to the list take O(1), we get that the function takes O(k), where k is the number of minimal values in the heap.

Enjoy.