I am aware that an array method flat exists. but I would like to get a better understanding on how ... and concat affect the time complexity.
function flat1(arr) {
return arr.reduce(
(flatArr, item) => {
flatArr.push(...(Array.isArray(item) ? flat1(item) : [item]))
return flatArr
},
[]
)
}
function flat2(arr) {
return arr.reduce(
(flatArr, item) => {
return flatArr.concat(Array.isArray(item) ? flat2(item) : item)
},
[]
)
}
My intuition is that both approaches take O(n^2) time complexity worse case, n being the number of item in the original array. Because both concat and ... are going to iterate through the array and it is going to take n for both operation. Is my understanding right?
Is one approach preferred over the other approach?
I will need to simplify the problem by not flattening recursively, but only a single level:
function flat1(arr) {
return arr.reduce((flatArr, item) => {
flatArr.push(...(Array.isArray(item) ? item : [item]))
return flatArr
}, [])
}
function flat2(arr) {
return arr.reduce((flatArr, item) => {
return flatArr.concat(Array.isArray(item) ? item : [item])
}, [])
}
Let's assume the number of elements in arr is n, and the average number of elements in each item array is m. (And items that are not arrays count into that average as 1).
both
concatand...are going to iterate through the array
Yes, they both need to iterate through the item given to them. But that is not the point. push does modify the flatArr and takes O(m) time to add O(m) new elements onto it.
However, concat does create a new array, and for that it does not need to only iterate item but also flatArr. Given flatArr contains on average O(n/2*m) items, the flatArr.concat(item) takes O(n/2*m + m) = O(n*m).
Since each of these operations is executed once for each item in the arr, we get
flat1 the time complexity O(n*m) andflat2 the time complexity O(n*n*m) which is worse.The time complexities of the recursive functions are way more complicated since they also depend on how many arrays you have on which nesting levels. I'm failing to even come up with a good metric to describe such data structure :-)