Big O Drills

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