Urban Hafner

CTM: Exercise 3-12

Posted by Urban Hafner Mon, 19 Sep 2005 10:16:32 GMT

The problem

Complexity of list flattening. Calculate the number of operations needed by the two versions of the Flatten function given in section 3.4.4. With n_ elements and maximal nesting depth _k, what is the worst-case complexity of each version?

My solution

First of all, I’d like to make clear that I’ve never been good at complexity analyses. Secondly, I first forgot to incorporate the k_. So I will first present my solution without the _k and then try to incorporate it. But there I got stuck. So if you have a correct solution please help me out!

1. For the Flatten using lists the worst-case is a list of n_ Elements which are nested into each other. Then the second branch of Flatten will be selected _n times, and there will be 2n calls to Flatten and n_ calls to Append. While the calls to Flatten are of O(_1) the runtime of the Append calls depend on the length of the first argument to Append. In this case the first call takes n steps, the second call (n – 1), and so on. All the Appends together take n * (n – 1) / 2 time. Together the runtime is of O(2n + n * (n – 1) / 2) which is the same as O(n^{2^}).

1. Incorporating k_ into this analysis the worst case is a list of _n/k Elements which are lists nested to depth k_. Then there are in the order of _n calls to Flatten and all the Append calls together take n/k x (2k 4(k-1) 8(k-2) + ...) time. This should be of O(n2^), but I don’t know how to prove it. And I don’t even see it :(

1. The analysis of Flatten with difference lists is much easier. As we have learnt in chapter 3 the append of two difference lists is of O(1_). So the only thing we have to look at are the number of calls to Flatten. As we have seen before in worst-case there are _n calls to Flatten, incorporating k_ there are even less. So it’s clear that this version of Flatten is of O(_n).