List unflattening: wrong running time
The analysis of unflatteningList() on page 57 is incorrect. Its (worst-case) running time is actually O(n*n). For lists like:
node_1 <--> node_2 <--> ... <--> node_N
where each node points to a single-item child list like: node_1->child = child_1, ... node_N->child = child_N
after flattening the list looks like:
node_1 <--> node_2 <--> ... <--> node_N <--> child_1 <--> ... <--> child_N
And unflatteningList() will examine child_N node N times, child_(N-1) node N-1 times, etc.
|
