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!