I am studying BigO Complexity and I am analyzing common JavaScript functions and algorithms to get a good grasp on the topic. Today, I am analyzing two ways of merging a large number of arrays inspired by the Steamroller problem. Is my BigO Analysis of these two methods are correct?
Assume that we are given m
Arrays (inside a parentArray), each having size n
. We can flatten these arrays into one via either of the following two loops:
// concat() way:
// Given parentArray of size m:
var res = [], i;
for (i = 0; i < m; ++i) {
res = res.concat(parentArray[i]);
}
// push.apply() way:
// Given parentArray of size m:
var res = [], i;
for (i = 0; i < m; ++i) {
Array.prototype.push.apply(res, parentArray[i]);
}
However, according to my analysis, the two algorithms should have different running times. In case 1, per iteration, concat()
creates a new Array, copies over the previous values and then puts in the new values. In case 2, per iteration, push.apply()
mutates the existing Array by just putting in the new values.
Thus, if my math is correct, concat()
of m
Arrays of size n
should have a complexity of

SUM FROM
i = 1
TOm
OF(i  1)O(n) + O(n)
=O(square(m)n)
since, at each stepi
, we must copy over the previous Array of size(i  1)n
and then copy the new values of the current Array of sizen
.
On the other hand, push.apply()
of the same should have a complexity of

SUM FROM
i = 1
TOm
OFO(n)
=O(mn)
since, at each step, we are only copying over the new values of the current Array of sizen
to an existing Array.
Is my analysis correct? I have Googled quite a bit and all I have found are benchmarks instead of an analysis which is what I am after.