What are the orders O(n) for the following methods of simultaneously finding the max/min of an array? Which is best? Are there better ways?
If I had to cycle the array beforehand for another reason (eg multiply each element by 10), would it be best to use option 2 and find the max/min at the same time as multiplying each element in the same forEach?
Option 1:
// This is surely 2n
let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
let max = Math.max(...a);
let min = Math.min(...a);
Option 2:
// What order is this?
let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
let max = Number.MIN_SAFE_INTEGER, min = Number.MAX_SAFE_INTEGER;
a.forEach(v => {max = Math.max(max, v); min = Math.min(min, v);});
Option 3:
// Is this 3n/2?
let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
a.sort((x,y) => x - y);
let max = a[a.length - 1];
let min = a[0];
Big O notation does not include coefficients, as it only deals with how they scale. O(n) has the same behavior as n increases as O(2n) would. You can think about it as about nested loops. If you have to do something for every element, that's O(n). If you have to do something for every pair of elements, that's O(n^2)
Big O does not allow you to compare performance of functions directly, and you could have two O(n) functions with vastly different speeds (imagine one is sleeping for 10 seconds per element, the other is sleeping 1 second per element). Similarly, at smaller scales, an O(n^2) function could outperform an O(n) function, but the O(n) function will, at a high enough n outperform the higher time complexity function
Option 1 is O(n) (you iterate over each element without nesting, even though you do it twice)
Option 2 is O(n) (you iterate over each element without nesting)
Option 3 depends on the JavaScript engine's implementation of Array.prototype.sort, but is certainly higher than guaranteed O(n). Worst case O(nlogn), but some implementations will take advantage of already ordered data (which you don't have) to sort more efficiently. See this answer for more detail