# Time complexity for recrusive deep flatten

seasick Source

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;
}
``````
javascriptrecursionbig-o

answered 6 days ago meowgoesthedog #1

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-trivial1 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 `push`ing2 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(input);

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).