Create a gist now

Instantly share code, notes, and snippets.

@tgray6 /Big-O-Drills
Last active Jul 11, 2018

Embed
What would you like to do?
Big O Drills
---ONE---
Even or odd: Constant time 0(1)
No matter the input, will always take 1 tick to determine even or odd.
https://repl.it/@tgray6/SizzlingSufficientEngineer
---TWO---
Are you Here:polynomial run time complexity (O(n^2)) **REVIEW**NOT WORKING AS INTENDED**
No idea how to make it work, moving on, I just know it is polynomial because it simply looks like it...
https://repl.it/@tgray6/YearlyFlatDominspector
---THREE---
Doubler: linear run time complexity (O(n))
It is possibly working as intended, it is called doubleArrayValues, but all this is doing is doubling the array totals [1,2,3] = 6
https://repl.it/@tgray6/linear-run-time-complexity-On
---FOUR---
Naive Search: linear run time complexity (O(n))
https://repl.it/@tgray6/Naive-Search-linear-run-time-complexity-On
https://repl.it/@tgray6/Naive-Search-linear-run-time-complexity-On
---FIVE---
Creating pairs: polynomial run time complexity (O(n^2))
function createPairs(arr) {
for (let i = 0; i < arr.length; i++) {
for(let j = i+1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
---SIX---
Computing fibonaccis: linear run time complexity (O(n))
A fibonacci sequence is one where every number is the sum of the previous two numbers in the sequence.
For example the following is a fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34.
The first number always starts at 1 (technically it is 0).
Then the second number is 0+1 = 1,
the third number is the sum of the first and the second numbers (1 + 2 = 3) and the sequence continues in a similar manner.
Here, we have a function generateFib that uses iteration to generate a fibonacci sequence. Determine its run time complexity in big O.
function generateFib(num) {
let result = [];
for (let i = 1; i <= num; i++) {
// we're adding the first item
// to the result list, append the
// number 0 to results
if (i === 1) {
result.push(0);
}
// ...and if it's the second item
// append 1
else if (i == 2) {
result.push(1);
}
// otherwise, sum the two previous result items, and append that value to results.
else {
result.push(result[i - 2] + result[i - 3]);
}
}
// once the for loop finishes
// we return `result`.
return result;
}
---SEVEN---
An Efficient Search: logarithmic run time complexity (O(log n))
In this example, we return to the problem of searching using a more sophisticated approach than in naive search, above.
Assume that the input array is always sorted.
function efficientSearch(array, item) {
let minIndex = 0;
let maxIndex = array.length - 1;
let currentIndex;
let currentElement;
while (minIndex <= maxIndex) {
currentIndex = Math.floor((minIndex + maxIndex) / 2);
currentElement = array[currentIndex];
if (currentElement < item) {
minIndex = currentIndex + 1;
}
else if (currentElement > item) {
maxIndex = currentIndex - 1;
}
else {
return currentIndex;
}
}
return -1;
}
---EIGHT---
Random element: constant run time complexity (O(1))
function findRandomElement(arr) {
return arr[Math.floor(Math.random() * arr.length)];
}
---NINE---
Is it prime? linear run time complexity (O(n))
function isPrime(n) {
// if n is less than 2 or a decimal, it's not prime
if (n < 2 || n % 1 != 0) {
return false;
}
// otherwise, check if `n` is divisible by any integer
// between 2 and n.
for (let i = 2; i < n; ++i) {
if (n % i == 0) return false;
}
return true;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment