using reduce inside a for loop make the code O(n) complexity or higher like O(n^2) or another kind?

Question

For an interview, they ask me to do some exercises and the 3rd one was the following:

We have an unknown quantity of elements in a vector/array v1 with random integer numbers.

• Made a v2 vector/array with the same length of v1 in that the v2[k] is the product of all the elements of v1 except v1[k]
• try to do it without the division operator and with complexity O(n).

And I do the following code:

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7]; //it's just an example array
const l = v1.length;
let v2 = [];

for (let i = 0; i < l; i++) {
  let segment = v1.splice(0, 1); // save the number of the position in array that it'll exclude de product
  let product = v1.reduce((total, number) => { return total * number; }, 1);
  v2.push(product); // add the result to the v2 array at the position of the number of v1 array
  v1.push(segment); // is necesary to add again the segment of the v1 array to keep the original length
}

console.log('v2', v2);

/* Results Reference
product of all array    42674688    
product - position 00   10668672    
product - position 01   21337344    
product - position 02   6096384 
product - position 03   5334336 
product - position 04   7112448 
product - position 05   6096384 
product - position 06   4741632 
product - position 07   14224896    
product - position 08   21337344    
product - position 09   7112448 
product - position 10   6096384  
*/

My question is:

• Is my code an O(n) complexity? or is O(n^2)? or another kind of complexity?

thanks

Answer 1

Your code is not O(n) because for each element of array v1, you run the .reduce() function that runs through the whole array, so it's O(n^2).

You can do it by calculating the total product, then iterating once through the v1 array and pushing the total / current to the v2 array. That way you will have the desired result with O(n) complexity.

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7];
const v2 = [];

const productTotal = v1.reduce((res, curr) => res * curr);

v1.forEach((el) => v2.push(productTotal/el));

console.log(v2);

So in total you iterate twice through the v1 array - once to calculate productTotal and once to calculate v2, so in fact, that's a O(2n) complexity, but we can ignore the 2 because it's still O(n).

To achieve it without division you could use a trick, and instead of using division directly, you could use multiplication and the power of -1 (don't know if that counts):

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7];
const v2 = [];

const productTotal = v1.reduce((res, curr) => res * curr);

v1.forEach((el) => v2.push(productTotal*Math.pow(el, -1)));

console.log(v2);

Answer 2

As already answered by @Sebastian Kaczmarek, the time complexity of your code is O(n^2) since the time complexity of .reduce is O(n) and .reduce is in the for loop which runs through the whole array.

One possible solution of which time complexity is O(n) and does not use division operator is the following:

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7];
const length = v1.length;

const v2 = new Array(length);

const listOfAccFromStart = new Array(length);
const listOfAccFromEnd = new Array(length);

let accFromStart = 1;
for (let i = 0; i < length; i++) {
  accFromStart *= v1[i];
  listOfAccFromStart[i] = accFromStart;
}

let accFromEnd = 1;
for (let i = length - 1; i >= 0; i--) {
  accFromEnd *= v1[i];
  listOfAccFromEnd[i] = accFromEnd;
}

v2[0] = listOfAccFromEnd[1];
v2[length - 1] = listOfAccFromStart[length - 2];
for (let i = 1; i < length - 1; i++) {
  v2[i] = listOfAccFromStart[i - 1] * listOfAccFromEnd[i + 1];
}

console.log('v2', v2);

It saves the accumulated product values from start to listOfAccFromStart and the accumulated product values from end to listOfAccFromEnd. And it uses the saved values to set v2. Its time complexity is O(n) and its space complexity is O(n).