Instantly share code, notes, and snippets.

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

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; }