0
$\begingroup$

The problem is this: Let us have an int array of length n. Find an algorithm to determine if the array represents a min-d-heap.

My solution: We start from the first index in the array, and compare its value to the value of its children (all the nodes at locations $i*d+k$ where $k \in \{1,2,...d\}$, assuming we start the array at index 0). We do it for every index until we reach an index that "has no children", meaning $i*d+1>n-1$. If at every point the value of the parent's key was lower than the value of all of its children' keys we return $True$, meaning the array represents a min-d-heap.

Now - my problem is calculating the time complexity for this algorithm:

I have managed to prove that if we look at a "complete" d-tree, we get a time complexity of $O(n)$ worst case. This is my proof:

Let us assume the tree is of height $h$. We note that at the last level we have $d^{h-1}$ items. Now, we can show that the tree excluding the last level has $O(\frac{n}{d})$ items: $$\frac{\sum_{i=0}^{h-1}d^i}{d^{h-1}} = \frac{d^{h-1}-1}{(d-1)d^{h-1}} = O(\frac{1}{d})$$ Therefore, for every node excluding the last level we make $d$ comparisons, and we get that the time complexity for the algorithm is $O(d*\frac{n}{d}) = O(n)$.

My problem is that my proof was based on the fact that we have a complete tree. There are cases which are asymmetric and I found harder to prove for the general case. I did check it by hand and showed that it is indeed the same time complexity but couldn't prove it.

Would like your help in the last part, Thanks!

$\endgroup$
  • $\begingroup$ A simpler algorithm: Check every element (except the root) with its parent; fail if the parent is greater. That obviously does one check for each of $n-1$ elements. (That's the same algorithm, really. It's just turned on its head.) $\endgroup$ – rici Jun 13 '17 at 1:31
  • $\begingroup$ @rici wow that is extremely simple, thanks! So even if I don't change the algorithm by hand, I can show the complexity by comparing it to this alogirhtm (which is the same but turned on its head as you stated). I would still be happy to see if there is a way to prove the time complexity by hand (as I started above) but for the general case, would love to know that for general knowledge as well (probably will be useful in the future). $\endgroup$ – Mickey Jun 13 '17 at 5:53
1
$\begingroup$

Apart from the answer given by rici in the comment to the question, I've come up today with an answer to prove this exact algorithm's time complexity, and it's pretty simple:

Since the algorithm goes over all of the parents in the heap (i.e all the nodes that have children), we only need to look at them while calculating the time complexity. The first parent is obviously the first item in the array. The last parent, is the parent of the last item in the array. The last item in the array is located at index $n-1$, therefore the parent of the last item (and the last parent) is located at index $\lfloor\frac{n-2}{d}\rfloor$ which is $O(\frac{n}{d})$. Therefore - we have $O(\frac{n}{d})$ parents in the array. For each parent we make $d$ comparisons, and finally we get the time complexity of $O(\frac{n}{d}*d) = O(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.