Complexity for checking if an array is a min-d-heap

Question

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!

Answer 1

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