Time complexity of Return Largest Numbers in Arrays from basic algorithm scripting

Hello, the question is Return Largest Numbers in Arrays from basic algorithm scripting.

Im confused on the time complexity of my solution whether it would be O(2n) or if it will be O(n^2)

let me know what you guys think? will it be 2n as it is one loop or will it be n^2 as the single loop has first statement initializing i but second statement checks with value of j

function largestOfFour(arr) {
  let arr2 = [];
  let j = 0;
  let max = -Infinity;
  
    //loop from i=0,1,2,3 until j < 4  
    for(let i = 0; j < arr.length; i++) {
      //store max value among the 4 values 
    if(max < arr[j][i]) {
      max = arr[j][i];
    }
    //once i === 3,
    // increment j
    //reinitialize i to -1 so it becomes 0 when current loop ends
    //reinitialize max for next array
    if((i / 3 === 1)) {
      j++;
      i = -1;
      arr2.push(max);
      max = -Infinity;
    } 
  }
  return arr2;
}

largestOfFour([[4, 9, 1, 3], [13, 35, 18, 26], [32, 35, 97, 39], [1000000, 1001, 857, 1]]);

You have time complexity of O(n), but I would try to clean up your loops because your incrementing of i and j is pretty messy and nonstandard.

1 Like

yea i had been learning about the sliding window method, and i think i tried some weird form of implementation here, I’m guessing a while loop will look better here, but even then i would have to re initiate i = 0 or -1 as because of the shape of the array being multidimensional…

I would just make the outer loop over j and the inner loop over i. There is no reason to do anything more complex.

The for loop looks like it would run infinitely if arr.length is greater than 3. You i every time it reaches 3 to -1 and increment j by one. To be able to break out of that loop you need a condition that takes the value of j into account. I don’t see such a condition. Maybe I’m missing something.

The incrementing of j is at the bottom of the loop instead of in the loop head where it belongs.

yeah, just saw that the condition for the loop is j < arr.length, so it breaks out when j increments.

hopefully this one is cleaner and easier to read. but im still confused if its similar to a nested loop while working, why it would give a time complexity of O(n) and not n^2

    //loop infinitely from j = 0 till 3
    for(let j = 0; j < arr.length; j++) {
      //store max value among the 4 values of one subArray
    if(max < arr[i][j]) max = arr[i][j];

    //check condition for when j reaches end of its subarray value
    if((j === (arr.length-1))) {
      //reinitialize j to -1 so it becomes 0 when current loop ends
      j = -1;
      arr2.push(max);
      //reinitialize max for next subArray
      max = -Infinity;
      //increment i to go to next subArray
      i++;
    }
    //break out of loop once i has looped over all subArray and to avoid looping infinitely
    if(i === arr.length) {
      break;
    } 
  }
  return arr2;
}

You are still mixing two loops into a singe very confusing loop body. Do not do this. Make your loop bodies clear, simple, and independent.

You cannot change the complexity class of this algorithm by making a more complicated loop body. You still have to visit every member of every sub-array exactly once. Nested loops most clearly express this logic.

1 Like

alright then, i suppose brute force is the way for the basic algorithm section.

function largestOfFour(arr) {
  let max = -Infinity;
  let arr2 = [];

  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length; j++) {
      let temp = arr[i][j];
      temp > max ? (max = temp) : max;
    }
    arr2.push(max);
    max = -Infinity;
  }
  return arr2;
}

I did not say ‘brute force’. I said clear and simple. You did not change the complexity class by making the loop harder to read. There are algorithms in here where a different approach can reduce the complexity class but you still want the code in those algorithms to be clear.

check out this one Time complexity of Return Largest Numbers in Arrays from basic algorithm scripting - #11 by p.raksahb
should be easy to read, let me know if there’s something i can do to make it more clearer

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.