Time complexity for recrusive deep flatten

Question

What is the runtime for this recursive flatten function? My guess is that it's linear; can someone explain why?

const arr = [
  [14, [45, 60], 6, [47, [1, 2, [14, [45, 60], 6, [47, [1, 2]], 9]]], 9],
];

function flatten(items) {
  const flat = [];

  items.forEach(item => {
    if (Array.isArray(item)) {
      flat.push(...flatten(item));
    } else {
      flat.push(item);
    }
  });

  return flat;
}

I also would think that it's linear in the number of elements, because ultimately you need to touch each element once, as it gets moved to a single level array. — Tim Biegeleisen
@TimBiegeleisen although O(N) is intuitive, it depends on the recursive structure of the array, since intermediate buffers are being created for each nested array. — meowgoesthedog

meowgoesthedog meowgoesthedog · Accepted Answer · 2018-10-11T11:04:08

As pointed out in the comments, since each element is indeed touched only once, the time complexity is intuitively O(N).

However, because each recursive call to flatten creates a new intermediate array, the run-time depends strongly on the structure of the input array.

A non-trivial¹ example of such a case would be when the array is organized similarly to a full binary tree:

[[[a, b], [c, d]], [[e, f], [g, h]]], [[[i, j], [k, l]], [[m, n], [o, p]]]

               |
        ______ + ______
       |               |
    __ + __         __ + __
   |       |       |       |
 _ + _   _ + _   _ + _   _ + _
| | | | | | | | | | | | | | | | 
a b c d e f g h i j k l m n o p

The time complexity recurrence relation is:

T(n) = 2 * T(n / 2) + O(n)

Where 2 * T(n / 2) comes from recursive calls to flatten the sub-trees, and O(n) from pushing² the results, which are two arrays of length n / 2.

The Master theorem states that in this case T(N) = O(N log N), not O(N) as expected.

_{1) non-trivial means that no element is wrapped unnecessarily, e.g. [[[a]]].}

_{2) This implicitly assumes that k push operations are O(k) amortized, which is not guaranteed by the standard, but is still true for most implementations.}

A "true" O(N) solution will directly append to the final output array instead of creating intermediate arrays:

function flatten_linear(items) {
  const flat = [];

  // do not call the whole function recursively
  // ... that's this mule function's job
  function inner(input) {
     if (Array.isArray(input))
        input.forEach(inner);
     else
        flat.push(input);
  }

  // call on the "root" array
  inner(items);  

  return flat;
}

The recurrence becomes T(n) = 2 * T(n / 2) + O(1) for the previous example, which is linear.

_{Again this assumes both 1) and 2).}

Time complexity for recrusive deep flatten

1 Answers