2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Jan 17, 2022 at 22:28
  • $\begingroup$ @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. $\endgroup$
    – Fred Jefferson
    Jan 17, 2022 at 22:37
  • $\begingroup$ You might be interested in the following question: cs.stackexchange.com/questions/3149/… $\endgroup$
    – Yuval Filmus
    Jan 18, 2022 at 7:08

1 Answer 1

Reset to default
0
$\begingroup$

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

Asymptotic notation in several variables is ambiguous. Often we use it when the expression in question is monotone increasing in all variables, which is not the case here, and so whenever using it, you should clarify what it means.

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.

For more on formalizations of asymptotic notation on several variables, see the answers to this question.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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