hard20 pts · first answer countsgraphslcatrees

Binary lifting memory and query cost

Binary lifting stores up[k][v], the 2^k-th ancestor of v. For n nodes, what are its memory use and query time for the k-th ancestor?

A.O(n) memory and O(1) per queryB.O(n^2) memory and O(1) per queryC.O(n log n) memory and O(log n) per queryD.O(n log n) memory and O(1) per query

Discussion 0

Join free to post in the discussion.