Complexity for checking if an array is a min-d-heap
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)$.