Ch3, Ex12

Worst case happens when all n elements are nested with depth k. For example let say k=2 and n=3 then list of 1,2,3 would look like [[[1]] [[2]] [[3]]]

Complexity of the version that works with simple versions of list is O(n*k) because for each element there are k "unnestings" to be done. Or may be understand as follow
T(n,k) = T(1,k-1) + T(n-1,k)+ A(1,n-1) + c where A(m,n) denotes time taken to append a list of n elems on a list of m elems. T(n,k) = nT(1,0)+(n*k-n-1)T(0,0)+constant which is O(n*k)

Complexity of the version that works with difference lists is also O(n*k) with same reasoning as above but the constant value is relatively too small because cost of append operations is saved completely.