Search code examples
algorithmheapbig-otree-traversal

Big O for this recursive algorithm

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 ?

Solution

  • 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(N2) worst case.