// What is the Big O of the below function? (Hint, you may want to go line by line)
function funChallenge(input) {
let a = 10; // O(1)
a = 50 + 3; // O(1)
for (let i = 0; i < input.length; i++) { // O(n)
anotherFunction(); // O(n)
let stranger = true;
a++; // O(n)
}
return a; // O(1)
}
function anotherFunction(){
console.log('howdy');
}
const result = funChallenge([0, 1, 2, 3, 4, 5]);
console.log(result, 'BIG O: 3 + 4n')
// What is the Big O of the below function? (Hint, you may want to go line by line)
function anotherFunChallenge(input) {
let a = 5;
let b = 10;
let c = 50;
for (let i = 0; i < input; i++) {
let x = i + 1;
let y = i + 2;
let z = i + 3;
}
for (let j = 0; j < input; j++) {
let p = j * 2;
let q = j * 2;
}
let whoAmI = "I don't know";
}
// BIG O(4 + 2n)
//
function printFirstItemThenFirstHalfThenSayHi100Times(items) {
console.log(items[0]);
var middleIndex = Math.floor(items.length / 2);
var index = 0;
while (index < middleIndex) {
console.log(items[index]);
index++;
}
for (var i = 0; i < 100; i++) {
console.log('hi');
}
}
// BIG O(3 + 2n)
//Log all pairs of array
const boxes = ['a', 'b', 'c', 'd', 'e'];
function logAllPairsOfArray(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
console.log(array[i], array[j])
}
}
}
logAllPairsOfArray(boxes)
//
function printAllNumbersThenAllPairSums(numbers) {
console.log('these are the numbers:');
numbers.forEach(function(number) {
console.log(number);
});
console.log('and these are their sums:');
numbers.forEach(function(firstNumber) {
numbers.forEach(function(secondNumber) {
console.log(firstNumber + secondNumber);
});
});
}
printAllNumbersThenAllPairSums([1,2,3,4,5])
//#5 Space complexity O(1)
function boooo(n) {
for (let i = 0; i < n; i++) {
console.log('booooo');
}
}
// #6 Space complexity O(n)
function arrayOfHiNTimes(n) {
var hiArray = [];
for (let i = 0; i < n; i++) {
hiArray[i] = 'hi';
}
return hiArray;
}
arrayOfHiNTimes(6)
// Given 2 arrays, create a function that let's a user know (true/false) whether these two arrays contain any common items
//For Example:
//const array1 = ['a', 'b', 'c', 'x'];//const array2 = ['z', 'y', 'i'];
//should return false.
//-----------
//const array1 = ['a', 'b', 'c', 'x'];//const array2 = ['z', 'y', 'x'];
//should return true.
// 2 parameters - arrays - no size limit
// return true or false
function containsCommonItem(arr1, arr2) {
for (let i=0; i < arr1.length; i++) {
for ( let j=0; j < arr2.length; j++) {
if(arr1[i] === arr2[j]) {
return true;
}
}
}
return false
}
//O(a*b)
//O(1) - Space Complexity
const array1 = ['a', 'b', 'c', 'x'];
const array2 = ['z', 'y', 'a'];
function containsCommonItem2(arr1, arr2) {
// loop through first array and create object where properties === items in the array
// can we assume always 2 params?
let map = {};
for (let i=0; i < arr1.length; i++) {
if(!map[arr1[i]]) {
const item = arr1[i];
map[item] = true;
}
}
// loop through second array and check if item in second array exists on created object.
for (let j=0; j < arr2.length; j++) {
if (map[arr2[j]]) {
return true;
}
}
return false
}
//O(a + b) Time Complexity
//O(a) Space Complexity
// containsCommonItem2(array1, array2)
function containsCommonItem3(arr1, arr2) {
return arr1.some(item => arr2.includes(item))
}
containsCommonItem(array1, array2)
containsCommonItem2(array1, array2)
containsCommonItem3(array1, array2)
// Naive
function hasPairWithSum(arr, sum){
var len = arr.length;
for(var i =0; i<len-1; i++){
for(var j = i+1;j<len; j++){
if (arr[i] + arr[j] === sum)
return true;
}
}
return false;
}
// Better
function hasPairWithSum2(arr, sum){
const mySet = new Set();
const len = arr.length;
for (let i = 0; i < len; i++){
if (mySet.has(arr[i])) {
return true;
}
mySet.add(sum - arr[i]);
}
return false;
}
hasPairWithSum2([6,4,3,2,1,7], 9)
