Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Even or odd: Constant time O(1)
- function isEven(value){
- //determine if a value is even if remainder is 0 after division
- //I assume the complexity is here, at the math operation but I'm not sure.
- if (value % 2 == 0){
- //if remainder 0, return true
- return true;
- }
- else
- return false;
- }
- Are you here: Polynomial time O(n^k) O(n^2)
- function areYouHere(arr1, arr2) {
- // Nested loops are characteristic of O(n^k) time apparently
- // First loop over the first array
- // I'm assuming that the loop is the complex part of the algorithm but i'm not sure.
- // I don't think that assigning variables to values would result in increased time complexity but again, i'm not sure.
- // If i is less than the length of array 1, increment by 1
- for (let i=0; i<arr1.length; i++) {
- // assign the value of the index in arr1 to el1
- const el1 = arr1[i];
- // Second loop(nested loop) over the second array(nested array)
- for (let j=0; j<arr2.length; j++) {
- const el2 = arr2[j];
- if (el1 === el2) return true;
- //If another loop was implemented I think that the complexity would be O(n^3) and so on.
- }
- }
- return false;
- }
- Doubler: Linear time O(n) O(1)
- function doubleArrayValues(array) {
- //Loop over the input and double each index
- for (let i=0; i<array.length; i++) {
- array[i] *= 2;
- }
- return array;
- }
- Naive Search: Constant time O(1) WRONG it's Linear time but I don't know why.
- function naiveSearch(array, item) {
- // Is the loop considered one operation? Or is each iteration considered one operation?
- // I'm assuming this is Constant time as it's accessing an array item.
- for (let i=0; i<array.length; i++) {
- if (array[i] === item) {
- return i;
- }
- }
- }
- Creating pairs: Polynomial time O(n^2)
- function createPairs(arr) {
- //I'm guessing because I am confused. I only say Polynomial time
- //because of the nested loops.
- //Loop over first array
- for (let i = 0; i < arr.length; i++) {
- //Loop over 2nd array one index space ahead of first array(I think).
- //I think this will allow comparisons to be made between array elements/indices
- //in order to determine pairs/like elements
- for(let j = i+1; j < arr.length; j++) {
- //
- console.log(arr[i] + ", " + arr[j] );
- }
- }
- }
- Computing fibonaccis: Constan time O(1) but i'm just guessing. WRONG it's Linear time O(n) which kind of makes sense to me.
- function generateFib(num) {
- let result = [];
- for (let i = 1; i <= num; i++) {
- //The comments below are taken directly from the code snippet and are not mine.
- // 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;
- }
- An Efficient Search: Logarithmic time O(log(n))
- function efficientSearch(array, item) {
- let minIndex = 0;
- let maxIndex = array.length - 1;
- let currentIndex;
- let currentElement;
- while (minIndex <= maxIndex) {
- //Return an integer that is <= the first element in the array added to the last element in the array and divide it by 2.
- //It appears to cut in half, the array.
- //currentIndex has the value of the math operation.
- currentIndex = Math.floor((minIndex + maxIndex) / 2);
- //currentElement has the value of the index position in the array, which is in the middle of the array, I think.
- currentElement = array[currentIndex];
- // This appears to be a loop. If the currentElement is less than item, increment by 1 and assign that value to minIndex.
- // Does this have the effect of searching the "left" side of the divided array? Or is it the "right" side?
- if (currentElement < item) {
- minIndex = currentIndex + 1;
- }
- // Does this have the effect of searching the "right" side of the array, or "left" side?
- else if (currentElement > item) {
- maxIndex = currentIndex - 1;
- }
- else {
- return currentIndex;
- }
- }
- return -1;
- }
- Random element: Exponential time O(2^n) WRONG it's Constant time O(1)
- function findRandomElement(arr) {
- //I think this will return the product of a random number from the array times the number of elements in the array.
- //I'm guessing Exponential time due to the multiplication operation. Either that or Constant time. (I was close.).
- //I should have known because it's a simple math operation.
- return arr[Math.floor(Math.random() * arr.length)];
- }
- Is it prime: Linear time O(n)
- function isPrime(n) {
- //Comments below are taken from the code snippet and are not mine.
- // if n is less than 2 or is 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement