Return Largest Numbers in Arrays - which of these two has the faster running time?

JavaScript
1

Tell us what’s happening:

Both of the codes below pass all the tests, but which one will perform faster?

In the first case, I sort the four given arrays in arr in a descending manner and just push the first element of each of the arrays into a separate array (res).

In the second case, I traverse each of the sub-arrays in arr, find the highest element from them manually and push them to the new array (res).

Your code so far

Sorting the array approach

function largestOfFour(arr) {
  // You can do this!
  var res = [];
  
  for (var i = 0; i < arr.length; i++) {
    arr[i].sort(function(a, b) {
      return b - a;
    });
    res.push(arr[i][0]);
  }
  
  return res;
}

largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);

Manual iterative approach:

function largestOfFour(arr) {
  // You can do this!
  var res = [];
  
  for (var i = 0; i < arr.length; i++) {
    var highestNum = Number.MIN_VALUE;
    
    for (var j = 0; j < arr[i].length; j++) {
      if (arr[i][j] > highestNum) highestNum = arr[i][j];
    }
    res.push(highestNum);
  }
  
  return res;
}

largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);

Your browser information:

Your Browser User Agent is: Mozilla/5.0 (X11; Linux x86_64; rv:58.0) Gecko/20100101 Firefox/58.0.

Link to the challenge:

2

While JavaScript’s sort method can have different running times depending on the platform, we can assume that it’s going to use an optimal strategy and will run in O(n * log n) time. In an array of m number of sub-arrays, the running time would be O(nm * log n). With your manual approach, you’re just iterating through the inner array without performing any sort routine which makes the runtime linear to the size of the input. In total, that’s O(n * m), which is smaller than the first algorithm, making your iterative approach faster. Exactly how much faster depends on the input as the larger m gets, the slower the sorted algorithm would go.

2 Likes
3

You can use console.time() to see how long it takes to run a particular operation. This timing is only based on your computer, and can change depending on what else you are running.

something like this call, after your function you want to test:

console.time('first function'); // 'first function' is just a label, you can call it anything
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);
console.timeEnd('first function');
1 Like