Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save utsukushiihime/c75c6535341e2490e497973a670bc3d7 to your computer and use it in GitHub Desktop.
Save utsukushiihime/c75c6535341e2490e497973a670bc3d7 to your computer and use it in GitHub Desktop.

Big-O Notation Exercises

What is the worst-case time complexity for the following algorithms?

#1

function wordOccurrence(word, phrase){
  let result = 0
  const array  = phrase.split(' ')
  for(let i = 0; i < array.length; i++){
    if(word.toLowerCase() === array[i].toLowerCase()){
      result++;
    }
  }
  return result
}

#2

function bubble_sort(list){
  for(let i = 0; i < list.length - 1; i++){
    for(let j  = 0; j < list.length - 2; j++){
      if(list[j+1] < list[j]){
        const temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
  return list;
}

#3

function bobIsFirst(people){
  return people[0] == 'bob'
}

#4

function isPalindrome(input){
  const stack = [];
  let output = "";
  for(let i = 0; i < input.length; i++){
    stack.push(input[i]);
  }
  while(stack.length){
    output += stack.pop();
  }
  return output == input
}

#5

function sumOfDivisors(n){
  let result = 0;
  let i = 1;
  while(i < n){
    if( n % i == 0){
      result += i;
    }
    i++;
  }
  return result
}

#6

function printAllNumbersThenSumPairs(numArray){
  numArray.forEach((num)=>{
    console.log(num);
  });
  numArray.forEach((num, index)=>{
    if(index < numArray.length - 1){
      console.log(num + numArray[index+1])
    }
  });
}

#7

function isPrime(num){
  if(num == 1 || num == 2){
    return false
  }
  for(let i = 2; i < num - 1; i++){
    if(num % i == 0){
      return false
    }
  }
  return true
}

#8

function calculateFactorial(n){
  if(n === 0){
    return 1;
  }else{
    return n * calculateFactorial(n-1);
  }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment