/* ===================================================================
Even or Odd
====================================================================*/
Answer: Constant Time - O(1)
Reason: Function only takes on value and makes a simple if then comparison
There are no extra function calls, loops, or anything to increase the complexity

function isEven(value){
  if (value % 2 == 0){
    return true;
  }
  else
    return false;
}

/* ===================================================================
Are You Here?
====================================================================*/

Answer: Polynomial Time - O(n^k)
Reason: Function takes two arrays with n length, It initiates a for loop
that looks at each item in the array. For each item in the first array,
it initiates a second for loop that looks through each item in the second array
If an item in the second array equals the item in the first array, it returns true
Because this is a for loop nested inside a for loop, the run time increases polynomially
with the lengths of each array.

function areYouHere(arr1, arr2) {
    for (let i=0; i<arr1.length; i++) {
        const el1 = arr1[i];
        for (let j=0; j<arr2.length; j++) {
            const el2 = arr2[j];
            if (el1 === el2) return true;
        }
    }
    return false;
}


/* ===================================================================
Doubler
====================================================================*/
Answer: Linear Time - O(n)
Reason: Function takes an array and doubles each item in the array.
The run time increases in a linear relation to the amount of items in the array

function doubleArrayValues(array) {
    for (let i=0; i<array.length; i++) {
        array[i] *= 2;
    }
    return array;
}

/* ===================================================================
Naive Search
====================================================================*/
Answer: Linear - O(n)
Reason: Function takes an array and looks for the item in the array,
and returns the index of the item - essentially indexOf. This is linear because
it goes through the array one time comparing the item with the current index. Best case
scenario it only takes one try, worst case it takes the entire length of the array. Therefore,
it is linear.

function naiveSearch(array, item) {
    for (let i=0; i<array.length; i++) {
        if (array[i] === item) {
            return i;
        }
    }
}

/* ===================================================================
Creating Pairs
====================================================================*/
Answer: Polynomial - O(n^k)
Reason: This function creates pairs for numbers by pairing each item in the array
with every other item in the array at a larger index than it. Once it makes pair
(array[0], array[1]), it does not make pair (array[1], array[0]) on it's pass through for index 1.
Therefore the length of time in the second for loop is decreased with every pass through. That said,
it loops through the array at least once for every index in the array. Therefore, it has a polynomial run time complexity.

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


/* ===================================================================
Computing fibonaccis
====================================================================*/
Answer: Linear - O(n)
Reason: Function initiates one for loop that loops through every number
up to and including the argument. Within the for loop are simple conditional statements,
which have a constant run time complexity. The length of time it takes to complete this function
is directly related to the size of the argument passed into the function e.g. it'll take 3 loops for
num = 3, and 100 loops for num = 100

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


/* ===================================================================
An Efficient Search
====================================================================*/
Answer: Logarithmic - O(log(n))
Reason: This function calculates the index of the item argument
in the array argument. It does this by comparing the midpoint of the array
to the item, if it is greater it sets the min index to the midpoint plus one - if lesser, the max index
to the mid point minus one. In this way, it cuts the problem size by half each time until it either returns
the index of the item argument or returns -1.

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

/* ===================================================================
Random element
====================================================================*/
Answer: Constant O(1)
Reason: This function finds a random element in an array calculating a random
number within the array length and returning the item at that index. Regardless
of the array's length, it will return one number and require it to be called only once.
Therfore its run time complexity is constant.

function findRandomElement(arr) {
    return arr[Math.floor(Math.random() * arr.length)];
}


/* ===================================================================
Is it prime?
====================================================================*/
Answer: Linear - O(n)
Reason: This function divides the passed in number by every number between it and
2. Because it passes through every number once and only once, it is a linear relationship.
I believe the time could be cut in half by comparing the numbers between 2 and the num/2 because
if it isn't divisble by any number between two and it's half, then it won't be divisible by any number
greater than it's half.

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