{{ message }}

Instantly share code, notes, and snippets.

jhwheeler/bigONotation.js

Last active Sep 21, 2021
Big O Notation Exercises
 // 1. Even or odd function isEven(value){ if (value % 2 == 0){ return true; } else return false; } /* Answer: O(1). Constant run time complexity. Reasoning: Because you're only ever taking one value, there is no "loop" to go through. Even as the value gets bigger, you simply divide it by 2 and see whether it returns an integer or a float. */ // 2. Are You Here? function areYouHere(arr1, arr2) { //let ticks1, ticks2 = 0; for (let i=0; i item) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; } /* Answer: O(log n). Logarithmic run time complexity. Reasoning: Cutting `array.length` in half in each iteration, the time complexity increases slowly, in a logarithmic fashion. */ // 8. Random element function findRandomElement(arr) { return arr[Math.floor(Math.random() * arr.length)]; } /* Answer: O(1). Constant run time complexity. Reasoning: With no iteration occurring, selecting an element at random from an array has constant time complexity. */ // 9. Is It Prime? function isPrime(n) { if (n < 2 || n % 1 != 0) { return false; } for (let i = 2; i < n; ++i) { if (n % i == 0) return false; } return true; } /* Answer: O(n). Linear run time complexity. Reasoning: Disregarding the constant time it takes to check the first if condition, this function is linear, as it iterates through each item once and only once. */ // 10. Factorial of a number w/ recursion function factorialOf(n) { switch (n) { case 0: case 1: return 1; default: return n * factorialOf(n - 1); } } /* Answer: O(n). Linear run time complexity. Reasoning: This function is being called recursively n times before reaching the base case. */

ben8p commented Jan 7, 2019 • edited

 I think `// 2. Are You Here?` is `O(nm)` where `n` is for `array1` and `m` for `array2` For each element of `array1` we go to every element of `array2` And length of `array1` isn't related to `array2`

ArtOfBBQ commented Apr 3, 2019

 Thanks jhwheeler this was helpful to me~

saragonclapps commented Aug 4, 2019

 Thanks, it's a great contribution , i needed exercises the Big(O) notation.

jhwheeler commented Aug 5, 2019

 Glad to hear it helped you guys!

hgodinez89 commented Jun 3, 2020

 I agree with @ben8p, the exercise number #2 is O(arr1 * arr2) or O(nm) because the function has two different inputs, and their lengths could very well be different.

azmym commented Jun 27, 2020

 I agree with @ben8p , length of arr1 not the same as arr2 so will be O(n*m)

jhwheeler commented Jun 27, 2020

 I think `// 2. Are You Here?` is `O(nm)` where `n` is for `array1` and `m` for `array2` For each element of `array1` we go to every element of `array2` And length of `array1` isn't related to `array2` Good point, if the two arrays have different lengths, then it would be `O(n*m)` complexity instead of `O(n^2)`. Thanks for pointing this out, I'll update the gist to reflect this.

sommelon commented Aug 23, 2020

 Would be nice if there were some recursive functions

gitryder commented Dec 16, 2020

 @jhwheeler, please add this recursive function to the gist ``````// 10. Factorial of a number w/ Recursion function factorialOf(n) { switch (n) { case 0: case 1: return 1; default: return n * factorialOf(n - 1); } } /* Answer: O(n). Linear run time complexity. Reasoning: This function is being called recursively n times before reaching the base case. */ ``````

jhwheeler commented Dec 17, 2020

 @jhwheeler, please add this recursive function to the gist ``````// 10. Factorial of a number w/ Recursion function factorialOf(n) { switch (n) { case 0: case 1: return 1; default: return n * factorialOf(n - 1); } } /* Answer: O(n). Linear run time complexity. Reasoning: This function is being called recursively n times before reaching the base case. */ `````` @gitryder Done! Thank you for contributing :D

viniciusvasti commented Mar 8, 2021

 About `// 2. Are You Here?` I agree that arrays inputs may be different. But, isn't true that we analysis Big O thinking in the worst case? The worst case would happens when both arrays have the same size. Therefore I believe the Big O is O(n^2).

 I think `// 2. Are You Here?` is `O(nm)` where `n` is for `array1` and `m` for `array2` For each element of `array1` we go to every element of `array2` And length of `array1` isn't related to `array2` The point is to get the worst-case scenario here. The worst-case scenario means n==m, therefore it will always be O(N^2),