Minimum depth of a d-ary tree of n-elements

4k Views Asked by At

A d-ary tree is a rooted tree in which each node has at most d children

(c) Suppose the tree has n nodes. What is the minimum the depth could possibly be, in terms of n and d? You can leave your answer in big-O format.


Solution: (c) If the tree has n nodes, its depth k must satisfy $n\leq d^{k+1}$, and thus k is $\Omega(log_d n)$.

can someone please walk me through this solution and explain the reasoning behind this problem?