2

I've done a bit of research online about this solution and I'm seeing a lot of conflicting information, some stating it's exponential, some stating it's linear. I'm wondering what is the worst case scenario's time complexity of flattening an array utilizing recursion inside of a loop to flatten deeply nested structures?

This is my code:

const flattenDeep = (array) => {
  const flat = [];
  for (let element of array) {
    Array.isArray(element)
      ? flat.push(...flattenDeep(element))
      : flat.push(element);
  }
  return flat;
}
voo94083
  • 29
  • 1
  • 4
  • 3
    How are you measuring the size of the problem? – Scott Hunter Jan 21 '23 at 01:11
  • Why not just use [`Array.prototype.flat()`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flat)? – Heretic Monkey Jan 21 '23 at 01:18
  • I'm not sure about how efficiently the `...flattenDeep(element)` expansion can be implemented; that could push it beyond linear. In theory the work can be linear, and as @HereticMonkey notes, `array.flat(Infinity)` already exists (and is almost certainly implemented to do linear work in number of elements in the final result plus maximum depth to be flattened), so reinventing the wheel is unnecessary. – ShadowRanger Jan 21 '23 at 01:26
  • 1
    Without specific shape data/limits it is a fairly meaningless measure, but it is the sum of the lengths of all nested arrays, so linear, but unknown. – pilchard Jan 21 '23 at 01:28
  • 2
    and [Big O of Recursive Methods](https://stackoverflow.com/questions/11750226/big-o-of-recursive-methods) – pilchard Jan 21 '23 at 01:33
  • 1
    "*I'm seeing a lot of conflicting information, some stating it's exponential, some stating it's linear*" - thanks for doing that research, but can you share links to the claims you found? Tbh I cannot imagine an implementation with exponential time complexity, for sane measurements of the input size. – Bergi Jan 21 '23 at 02:06
  • @ScottHunter Hi Scott! I'm fairly new to calculating time complexity, when you say 'the size of the problem' are you referring to the size of the input to my function? An example of an input could be an array with nested elements, such as this: const arr2 = [[1, [2, 3, [4]]]] --- essentially I just want to understand it on a very basic level. – voo94083 Jan 21 '23 at 02:12
  • @Bergi I actually got exponential implementation from freecodecamp.... https://www.freecodecamp.org/news/flatten-array-recursion/ – voo94083 Jan 21 '23 at 02:23
  • @vodeks Thanks. Their conclusion "*the time complexity is going to be nearly exponential*" is just wrong (and backed up by nothing - it sounds more like a guess). Just as wrong as the next sentence "*Recursion is rarely used in production environments.*". And they do not really define the variable `n` precisely. Their whole approach at determining time complexity for their algorithm is flawed when they write "*when it comes to time complexity, it depends on the input*". It doesn't. The time complexity is a property of the algorithm, not the input. – Bergi Jan 21 '23 at 02:34
  • @pilchard While related, I do not think the answers you linked can answer this question – Bergi Jan 21 '23 at 02:48

2 Answers2

3

No, the code you've shown has neither exponential nor linear time complexity.

Before we can determine the complexity of any algorithm, we need to decide how to measure the size of the input. For the particular case of flatting an array, many options exist. We can count the number of arrays in the input, the number of array elements (sum of all array lengths), the average array length, the number of non-array elements in all arrays, the likelyhood that an array element is an array, the average number of elements that are arrays, etc.

I think what makes the most sense to gauge algorithms for this problem are the number of array elements in the whole input - let's call it e - and the average depth of these elements - let's call it d.

Now there are two standard approaches to this problem. The algorithm you've shown

const flattenDeep = (array) => {
  const flat = [];
  for (let element of array) {
    Array.isArray(element)
      ? flat.push(...flattenDeep(element))
      : flat.push(element);
  }
  return flat;
}

does have a time complexity of O(e * d). It is the naive approach, also demonstrated in the shorter code

const flattenDeep = x => Array.isArray(x) ? x.flatMap(flattenDeep) : [x];

or in the slightly longer loop

const flattenDeep = (array) => {
  const flat = [];
  for (const element of array) {
    if (Array.isArray(element)) {
      flat.push(...flattenDeep(element))
    } else {
      flat.push(element);
    }
  }
  return flat;
}

Both of them have the problem that they are more-or-less-explicit nested loops, where the inner one loops over the result of the recursive call. Notice that the spread syntax in the call flat.push(...flattenDeep(element)) amounts to basically

for (const val of flattenDeep(element)) flat.push(val);

This is pretty bad, consider what happens for the worst case input [[[…[[[1,2,3,…,n]]]…]]].

The second standard approach is to directly put non-array elements into the final result array - without creating, returning and iterating any temporary arrays:

function flattenDeep(array) {
  const flat = [];
  function recurse(val) {
    if (Array.isArray(val)) {
      for (const el of val) {
        recurse(el);
      }
    } else {
      flat.push(val);
    }
  }
  recurse(array);
  return flat;
}

This is a much better solution, it has a linear time complexity of O(e) - d doesn't factor in at all any more.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Your answers are usually superb, so maybe I’m misunderstanding, but it seems like you chose a strange combo of input metrics. This suggests we might be given the total number of arrays in the input and the average depth. Mapping this to tree language, that’s like being given the exact number of internal nodes and the average number of steps to a leaf. Implausible, right? – danh Jan 21 '23 at 04:28
  • Wouldn’t a more plausible input metric for a tree be, simply, the number of nodes in the tree? In array terms, that’s the total number of array elements whether they are terminal or themselves arrays. The complexity (taking your good advice to not double-visit with spread operations, etc) would be O(n) where n is the number of elements. – danh Jan 21 '23 at 04:29
  • @danh That's what I meant, "*the number of array elements (sum of all array lengths)*". – Bergi Jan 21 '23 at 12:10
  • Ah. Okay, but then we don’t need the average depth. Visiting siblings or descendants, same O. – danh Jan 21 '23 at 14:22
  • 1
    @danh I've already fixed that. Don't remember how I got to `O(e + d)`. – Bergi Jan 21 '23 at 14:25
-2

  • the exploration of a regular structure can be done, however, for models that use addressing it is necessary to control the exploration, otherwise it may have infinite recursion.. i.e:

    var a = [ 1, 2, 3 ]; var t = [ ]; t.push(a); t.push(t);

    console.log(t);

infinit loop example

  • action: check if your array value already explored.
Carlos Celso
  • 1