Graph Theory37 sections · 1633 units
Open in CourseQuiz: Binary Lifting Recurrence
Knowledge check
Check Your Understanding
The recurrence up[v][k] = up[up[v][k-1]][k-1] computes the -th ancestor. Why is this correct?
- A.It adds twice, which equals
- B.It multiplies the jump distance by each level
- C.It jumps steps from , then another from where you land
- D.It looks up the -th entry in the parent's row