# Asymptotic height of d-ary heap

I know that the height of a $$d$$-ary heap on $$n$$ nodes is $$\lceil (\log_d (n(d-1) + 1) - 1)\rceil$$, but I was wondering how to justify that that's $$\Theta(\log_d n)$$? I know the definition of $$\Theta, O, \Omega$$ if only one variable is involved. In particular, what is the formal definition of a function $$h(n,d)$$ being in $$\Theta(\log_d n)$$?

One can clearly upper bound the height by $$\log_d (n)+1$$, but why does that imply the height is in $$O(\log_d n)$$? The problem is that $$d$$ can exceed $$n$$, and if $$d$$ keeps increasing while $$n$$ is fixed, then $$\log_d n$$ will approach $$0$$.

Also, one can show that the height is at least $$\log_d (n(d-1) + 1) - 1\ge \log_d n - 1$$ for $$d$$ sufficiently large. Why is this in $$\Omega(\log_d n)$$?

• If $d>n$ then the height is $1$ (or $0$, depending on how you define it), since all nodes will be on the same level, so I don't see a problem with $\log_d(n)$ being small. Jan 17, 2022 at 22:28
• @nirshahar thanks. But what's the formal definition of $O(\log_d n)$? I don't think the following definition works: a function $h(n,d)$ is in $O(\log_d n)$ if there exist constants $c,d_0,n_0 > 0$ so that for all $n\ge n_0, d\ge d_0, h(n,d) \leq c\log_d n.$ In the case where $d > n$ and the height is obviously $1$ (provided $n > 1$), then as $d$ increases while $n$ stays fixed, $c\log_d n\to 0,$ which is why I'm having a problem. Jan 17, 2022 at 22:37
• You might be interested in the following question: cs.stackexchange.com/questions/3149/… Jan 18, 2022 at 7:08

Suppose that $$n \geq 1$$ and $$d \geq 2$$. On the one hand, $$\lceil \log_d(n(d-1)+1)-1 \rceil \leq \log_d(2dn) \leq \log_d n + 2.$$ On the other hand, $$\lceil \log_d(n(d-1)+1)-1 \rceil \geq \log_d(nd/2)-1 = \log_d n - 1.$$
In other words, your expression is equal to $$\log_d n$$ up to a constant additive term.
In particular, if we fix $$d$$ then your expression is $$\Theta(\log n)$$. You can say more: we can find constants $$c,C>0$$ such that your expression is bounded between $$c \log_d n$$ and $$C\log_d n$$.
I wouldn't spend too much time agonizing on the relation between your expression and the quantity $$\log_d n$$. Informally, your expression is very close to $$\log_d n$$. This can be formalized in several ways, as I indicated above. Informally, one could write that your expression is $$\Theta(\log_d n)$$, but this is somewhat ambiguous, and as you point out, is false when $$n$$ is small compared to $$d$$. Nevertheless, it can be made precise in various ways.