function isEven(value){ -- this function just takes one value so the data set is always 1
if (value % 2 == 0){ ---has one thing we are evaluating
return true; --returning true or false
}
else
return false;
}
Answer - Constant time O(1)
function areYouHere(arr1, arr2) { --takes two sets of data
for (let i=0; i<arr1.length; i++) { -- has a loop
const el1 = arr1[i];
for (let j=0; j<arr2.length; j++) { -- has a nested loop
const el2 = arr2[j];
if (el1 === el2) return true; -- trying to search to two items that match in the two data sets
}
}
return false;
}
Assuming the worst and that the very last items in both arrays match, we have to tick through Array1.length x Array2.length
so if A1 = 2 and A2 = 5 = 10, 2 and 6 = 12 2 and 7 14 2 and 8 16 3 and 5 15 3 and 6 18
so for every increase in either we increase by that number and the nest loop compounds the increase
Nested loops usually result in polynomial time. And since an increase in the the second array just adds another set number of ticks based on the first arrays length. so it isnt really growing exponentially
Answer: Polynomial Time O(n^2)
function doubleArrayValues(array) {
for (let i=0; i<array.length; i++) { - loop through the array
array[i] *= 2; -- just multiplying values by 2 -1 tick
}
return array; -- returning the array
}
This function is linear because the time it takes increases only based on the size of the array. It adds a tick for each new element.
Answer = Linear Time O(n)
function naiveSearch(array, item) {
for (let i=0; i<array.length; i++) { -loop based on length of dataset
if (array[i] === item) { -- simple comparison
return i;
}
}
}
This looks linear as well. The loop is based on the length of the data set so it would increase in time based on that. The worst case scenario is the item is the last in the array.
Answer: Linear Time O(n)
function createPairs(arr) {
for (let i = 0; i < arr.length; i++) {
for(let j = i+1; j < arr.length; j++) { --interesting here they add 1 to the the i - meaning the loop gets smaller as
console.log(arr[i] + ", " + arr[j] ); --it progresses
}
}
}
This one has a nested loop based on the size of the array. But the second loop cuts down on the interations as it gets deeper into the first loop. So while I thought at first it was Polynomial Time because of the nested loops, I think it might be Logorithmic Time because it would increase in time at a slower rate than a Polynomial algorithm.
Answer: Logorithmic O(log(n))
function generateFib(num) { let result = []; for (let i = 1; i <= num; i++) { --the loop is based on the number value
// we're adding the first item
// to the result list, append the
// number 0 to results
if (i === 1) {
result.push(0); --the array is being added to, but not looped through
}
// ...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;
}
This function takes a value and the number of ticks if based on that value. The array in this function is being grown within the functions loop, but we are not looping over the array. So this is a linear time algorithm.
Answer Linear O(n)
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); --here we are finding the middle between min and max
currentElement = array[currentIndex]; --here we set the element to check
if (currentElement < item) {
minIndex = currentIndex + 1; --if the check element is less than the item we are looking for set min to one
bigger than element we are checking (wont look at anything less than that now)
}
else if (currentElement > item) { --if check el is bigger than search item, make max one less than check el,
wont search anthing bigger
maxIndex = currentIndex - 1;
}
else {
return currentIndex; --if those arent true we found it!
}
}
return -1; --or it couldnt be found
}
So on ever tick of the loop we shrink the data set we are searching. This is a logorithmic algorithm. Answer: Logorithmic O(log(n))
function findRandomElement(arr) {
return arr[Math.floor(Math.random() * arr.length)];
}
Here the function takes an array. It returns one element randomly in the array. We arent iterating over the array. Just muliplying by the length so this is not a linear time algorithm - just a constant time one.
Answer: Constant O(1)
function isPrime(n) {
// if n is less than 2 or a decimal, it's not prime
if (n < 2 || n % 1 != 0) { --simple check
return false;
}
// otherwise, check if `n` is divisible by any integer
// between 2 and n.
for (let i = 2; i < n; ++i) { --here is a loop increases in time based on the number value
if (n % i == 0) return false;
}
return true;
}
Answer: Linear O(n)