Minimal AVL Tree Recurrence

Algebra Level 3

Let T(d)T(d) denote the smallest size of an AVL tree of depth dd. Clearly T(0)=1T(0) = 1 and T(1)=2T(1) = 2

Which of the following recurrences does TT satisfy?

  1. T(d)=T(d1)+T(d2)T(d) = T(d-1) + T(d-2)
  2. T(d)=T(d1)+T(d2)+1T(d) = T(d-1) + T(d-2) +1
  3. T(d)=1+2T(d1)T(d) = 1 + 2T(d-1)
  4. T(d)=2T(d2)T(d) = 2T(d-2)
  5. T(d)=T(d/2)2T(d) = T(d/2)^2
  6. None of the above
×

Problem Loading...

Note Loading...

Set Loading...