Skip to content

Instantly share code, notes, and snippets.

@hdf
Created December 23, 2018 14:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hdf/17deb800a28046d09341f81f78426d58 to your computer and use it in GitHub Desktop.
Save hdf/17deb800a28046d09341f81f78426d58 to your computer and use it in GitHub Desktop.
Based on the array in question, and the counter value (you have to put the code for that in the function in question yourself), this function will tell us the time complexity of the function.
function BigO(arr, arr3) { // Second array is optional
this.accumulator = 0; // Can be set here, or when calling ClosestMatch
/* function factorial(n, i) {
if (n > 171) // Overflow prevention
return Infinity;
if (typeof i == 'undefined')
i = 1;
if (n < i)
return 1;
if (n === i)
return n
let half = (n + i) >> 1; // divide (n + 1) by 2 and truncate to integer
return factorial(half, i) * factorial(n, half + 1);
}*/
function factorial(n) { // Why not in standard Math object?
if (n > 171) // Overflow prevention
return Infinity;
let out = 1;
for (let i = 2; i <= n; i++)
out = out * i;
return out;
}
var Orders = [
["O(1)", "constant"],
["O(log log n)", "double logarithmic", n => Math.log2(Math.log2(n))],
["O(log n)", "logarithmic", n => Math.log2(n)],
["O(n)", "linear", n => n],
["O(n log n) = O(log n!)", "linearithmic, loglinear, or quasilinear", n => n * Math.log2(n)],
["O(n^c) 0<c<1", "fractional power", (n, c) => Math.pow(n, c), c => c > 0 && c < 1],
["O(n^2)", "quadratic", n => n * n],
["O(2^n)", "exponential", n => Math.pow(2, n)],
["O((log n)^c) c>0", "polylogarithmic", (n, c) => Math.pow(Math.log2(n), c), c => c > 0],
["O(n^c)", "polynomial or algebraic", (n, c) => Math.pow(n, c), c => c != 2],
["O(c^n) c>1", "exponential", (n, c) => Math.pow(c, n), c => c > 1 && c != 2],
["O(n!)", "factorial", n => factorial(n)]
];
this.ClosestMatch = (arr2, acc) => {
let n = arr.length;
if (typeof acc != 'number') // All parameters are optional
acc = this.accumulator;
if (typeof arr2 == 'number') // May be, that we get accumulator instead of a second array
acc = arr2;
if (typeof arr3 == 'object' && typeof arr2 != 'object') // Second array can be set here, in ClosestMatch, or at instantiation
arr2 = arr3;
let c = (typeof arr2 == 'object') ? arr2.length : undefined;
let min = acc - 1, i = 1, l = Orders.length, min_loc = 0;
while (i < l) {
if (Orders[i].length > 3 && (typeof c == 'undefined' || !Orders[i][3](c))) { // We skip if not applicable
i++;
continue;
}
let f = Orders[i][2](n, c);
//let d = Math.abs(acc - f);
let d = (f > acc) ? f - acc : acc - f;
//console.log('[' + i + '/' + (l - 1) + ']', Orders[i][0], f, 'diff:', d);
if (d < min) {
min = d;
min_loc = i;
}
i++; // Without c, we could just break here, but depending on the value of c, the order of Orders may vary, so we need to go through the whole list
}
return Orders[min_loc].slice(0, 2).concat(min);
}
}
var O = new BigO(new Array(10));
console.log(O.ClosestMatch(3628800));
console.log(O.ClosestMatch(new Array(5), 10000000));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment