Data Structures19 sections · 729 units
Open in Course

Quiz: Light Edge Bound

Why O(log n)?

Check Your Understanding

Why are there at most O(log n) light edges on any path to the root?

  1. A.Because the tree is balanced
  2. B.Because we remove half the nodes each step
  3. C.Because heavy chains have logarithmic length
  4. D.Because each light edge at least doubles the subtree size
Start the roadmap to answer the quizzes and solve the challenges