I have to write and solve a recurrence relation for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct using induction for perfect quad trees which are basically binary trees but with 4 children at each node rather than 2 and the leaf nodes in the deepest layer have no children. Nodes at precisely depth d is designated by n(d). For example, the root node has depth d=0, and is the only node at that depth, and so n(0) = 1
Does this mean it would be T(n)= 4T(n/4) + d ? then prove
I’m really confused and would appreciate any help or resources.