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;
}
javascriptrecursionbigo
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 runtime depends strongly on the structure of the input array.
A nontrivial^{1} 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 subtrees, and O(n)
from push
ing^{2} the results, which are two arrays of length n / 2
.
The Master theorem states that in this case
T(N) = O(N log N)
, notO(N)
as expected.
_{1) nontrivial 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).}