Big O drills

DRILL #1: EVEN OR ODD

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

ANSWER: Constant // O(1), the size of the input is irrelevant, it's just a simple math calculation.



DRILL #2: ARE YOU HERE

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

ANSWER: Polynomial // O(n^2), there is a loop nested inside another loop.



DRILL #3: DOUBLER

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

ANSWER: Linear // O(n), since the function has to perform a calculation on each 
element in the input array, it's complexity is directly proportional to the length of the input array.



DRILL #4: NAIVE SEARCH

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

ANSWER: Linear // O(n), even though it may find what it's looking for halfway through, the search is still linear bc
in a worst case scenario it would have to go through every single item in the input array individually.



DRILL #5: CREATING PAIRS

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

ANSWER: Polynomial // O(n^2), loop nested inside of another loop.



DRILL #6: COMPUTED FIBONACCIS

function generateFib(num) {
  let result = [];
  for (let i = 1; i <= num; i++) {
  
    if (i === 1) {
      result.push(0);
    }

    else if (i == 2) {
      result.push(1);
    }

    else {
      result.push(result[i - 2] + result[i - 3]);
    }
  }
  return result;
}

ANSWER: Linear // O(n), The larger the number, the more calculations it has to perform.



#7: AN EFFICIENT SEARCH

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

ANSWER: Logorithmic // O(log(n)), Because each iteration only deals with a 'chunk' or subset of the data instead of
each individual item in the input



#8: RANDOM ELEMENT

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

ANSWER: Constant // O(1), this function doesn't iterate (or use a recursive strategy) at all, it just grabs a random item from
the input array.



#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: Linear // 0(n), since it iterates through every number between 2 and n to check divisibility, the bigger n is,
the longer this function could possibly take.



GIST DRILL #1: GENERATE BINARY

function generateBinary(n, i=0, toAdd='', s='') {
    s += toAdd;
    if (i === n) {
        console.log(s);
        return;
    }

    generateBinary(n, i+1, 0, s);
    generateBinary(n, i+1, 1, s);
}

generateBinary(3);

ANSWER:Exponential // O(2^n), because there are 2 recursive calls inside of each call



GIST DRILL #2: COUNTING SHEEP

function countSheep(num){

    if(num === 0){
        console.log(`All sheep jumped over the fence`);
    } 

    else{
        console.log(`${num}: Another sheep jumps over the fence`);
        countSheep(num-1);
    }
}
countSheep(10);

ANSWER: Linear // O(n), it iterates through each "sheep" represented by the number you input, the bigger the number, the more
iterations.



GIST DRILL #3: ARRAY DOUBLE

function double_all(arr) {
    if (!arr.length) {
        return [];
    }
    return [arr[0] * 2, ...double_all(arr.slice(1))];
}
var arr = [10,5,3,4];
console.log(double_all(arr));

ANSWER: Linear // O(n), it iterates over each element in the input array and doubles it.



GIST DRILL #4: REVERSE STRING

function reverse(str) {
    if (str.length < 2) {
        return str;
    }
    return reverse(str.slice(1)) + str[0];
}
console.log(reverse("tauhida"));

ANSWER: Linear // O(n), uses recursive method to process each letter in the input string, moving it to the front of the output
string. The longer your input, the more processing.



GIST DRILL #5: TRIANGULAR NUMBER

function triangle(n) {
    if (n < 2) 
        return n;
    return n + triangle(n - 1);
}

ANSWER: Linear // O(n), uses the recursive strategy to process each number between 2 and n - 
the bigger n is, the longer it will take



GIST DRILL #6: STRING SPLITTER

function split(str, sep) {
    var idx = str.indexOf(sep);
    if (idx == -1) 
        return [str];
    return [str.slice(0, idx)].concat(split(str.slice(idx + sep.length), sep))
}
console.log(split('1/12/2017', '/'));

ANSWER: Linear // O(n), it goes over each character in the input string to determine what to do, the longer your string
the longer this will take



GIST DRILL #7: BINARY REPRESENTATION

function convertToBinary(num){
    if(num>0){
        let binary = Math.floor(num%2);
        return (convertToBinary(Math.floor(num/2))+ binary);
    }else{
        return '';
    }


}
console.log(convertToBinary(25));

ANSWER: Logarithmic // O(log(n)), Since it divides the input by two on each recursive call, it effectively breaks it into
chunks: n = 2743 only takes slightly longer than n = 11



GIST DRILL #8: ANAGRAMS

function printAnagram(word){
    console.log(`The word for which we will find an anagram is ${word}`);
    anagrams(' ', word);

}
function anagrams(prefix, str){
    if(str.length <= 1){
        console.log(`The anagram is ${prefix}${str}`);
    } else {
        for(let i=0; i<str.length; i++){
            let currentLetter = str.substring(i, i+1);
            let previousLetters = str.substring(0,i);
            let afterLetters = str.substring(i+1);
            anagrams(prefix+currentLetter, previousLetters+afterLetters);
        }
    }

}
printAnagram("east");

ANSWER: Exponential // O(2^n), This function figures out every possible combination of letters in n, so as the length of n
increases, the possible combinations increases exponentially.



GIST DRILL #9: ANIMAL HIERARCHY

const AnimalHierarchy = [
    {id: 'Animals','Parent': null},
    {id: 'Mammals','Parent': 'Animals'},
    {id: 'Dogs','Parent':'Mammals' },
    {id: 'Cats','Parent':'Mammals' },
    {id: 'Golden Retriever','Parent': 'Dogs'},
    {id: 'Husky','Parent':'Dogs' },
    {id: 'Bengal','Parent':'Cats' }
]

// ==============================
function traverse(AnimalHierarchy, parent) {
    let node = {};
    AnimalHierarchy.filter(item => item.Parent === parent)
                   .forEach(item => node[item.id] = traverse(AnimalHierarchy, item.id));
    return node;  
}
console.log(traverse(AnimalHierarchy, null));

ANSWER: Linear // O(n), This function has to process each item (object) in the Animal Hierarchy array, thus it's linear - the 
more objects in that array, the longer it will take to run the function in direct proportion.



GIST DRILL #10: FACTORIAL

function factorial(n) {  

  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

console.log(factorial(5));

ANSWER: Linear // O(n), This function runs through every number between 0 and n, thus is linear.



GIST DRILL #11: FIBONACCI

function fibonacci(n) {

  if (n <= 0) {
    return 0;
  }

  if (n <= 2) {
    return 1;
  }	

  return fibonacci(n - 1) + fibonacci(n - 2);	
}
console.log(fibonacci(7));

ANSWER: Exponential // O(2^n), There are two recursive calls for every call - so the function gets exponentially more complex
for bigger values of n.



GIST DRILL #12: ORGANIZATIONAL CHART

var organization = {
	"Zuckerberg": {		
		"Schroepfer": {
			"Bosworth": {
				"Steve":{},
				"Kyle":{},
				"Andra":{}
			},
			"Zhao": {
				"Richie":{},
				"Sofia":{},
				"Jen":{}
			},
			"Badros": {
				"John":{},
				"Mike":{},
				"Pat":{}
			},
			"Parikh": {
				"Zach":{},
				"Ryan":{},
				"Tes":{}
			}
		},
		"Schrage": {
			"VanDyck": {
				"Sabrina":{},
				"Michelle":{},
				"Josh":{}
			},
			"Swain": {
				"Blanch":{},
				"Tom":{},
				"Joe":{}
			},
			"Frankovsky": {
				"Jasee":{},
				"Brian":{},
				"Margaret":{}
			}
		},
		"Sandberg": {
			"Goler": {
				"Eddie":{},
				"Julie":{},
				"Annie":{}
			},
			"Hernandez": {
				"Rowi":{},
				"Inga":{},
				"Morgan":{}
			},
			"Moissinac": {
				"Amy":{},
				"Chuck":{},
				"Vinni":{}
			},
			"Kelley": {
				"Eric":{},
				"Ana":{},
				"Wes":{}
			}
}}};
function traverseB(node, indent=0) {
	for (var key in node) {
		console.log(" ".repeat(indent), key);
		traverseB(node[key], indent + 4);
	}
}

console.log(traverseB(organization));

ANSWER: Linear // O(n), it has to process every key in n individually, so the bigger the 
object n is (and the more nested it is), the more keys it has to process - in direct proportion.