search

pllk / cphb

Competitive Programmer's Handbook
2.9k stars 347 forks source link

Time complexity to generate table for logK lookup of K succesor of node n #77

Closed dpasiukevich closed 4 years ago

dpasiukevich commented 4 years ago

In chapter 16.3

Precalculating the values takes $O(n \log u)$ time, because $O(\log u)$ values are calculated for each node.

Shouldn't it be O(nu) time and O(nlogu) space? I'm wondering how can we reach u succesor of node n in logu time at this moment?

dpasiukevich commented 4 years ago

On the second thought, if we do this table generation in sort of "bottom up" approach, then for each node n we will already generate values for its every successor, and we can use succ(succ(x, k/2), k/2), thus making it O(nlogu)

Btw, your book is one of the best in the field, thank you for your work!