big-o-questions.md

big-o-questions.md

Big-O Notation Exercises

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

#1

def word_occurrence(word, phrase)
  result = 0
  array  = phrase.split(' ')
  for item in array
    result += 1 if item.downcase == word.downcase
  end
  return result
end

#2

def bubble_sort(list)
  for i in 0..(list.size - 1)
    for j in 0..(list.size - i - 2)
      if (list[j + 1] <=> list[j]) == -1
        list[j], list[j + 1] = list[j + 1], list[j]
      end
    end
  end
  return list
end

#3

def factorial(n)
  if n.zero?
    return 1
  else
    return n * factorial(n - 1)
  end
end

#4

def bob_is_first(people)
  return people.first == 'bob'
end

#5

def palindrome?(input)
  stack  = []
  output = ""
  input.each_char do |x|
    stack.push x
  end
  while not stack.empty?
    output << stack.pop
  end
  return (output == input)
end

#6

def sum_of_divisors(n)
  result = 0
  i      = 1
  while i < n
    if n % i == 0
      result += i
    end
    i += 1
  end
  return result
end

#7

def printAllNumbersThenAllPairSums(num_array) {
  num_array.each do |num|
    puts num
  end
  
  num_array.each_with_index do |num1|
    num_array[1..num_array.length-1].each do |num2|
      puts num1 + num2
    end
  end
}

#8

def is_prime(num)
  return false if num == 1
  return false if num == 2
  for i in 2..(num-1)
    if num % i == 0
      return false
    end
  end
  return true
end

#9

def guess_number(max, correct, counter=0)
  if(counter == correct)
    return "correct!"
  else
    guess_number(max, correct, counter+1)
  end
end

#10

def guess_number
  min = 1
  tries = 0
  guess = 0

  max = gets.chomp.to_i
  answer = rand(max) + 1

  while guess != answer
    guess = ((max + min) / 2).floor

    if guess == answer
      break
    end

    if guess < answer
      min = guess + 1
    end

    if guess > answer
      max = guess - 1
    end

    tries += 1
  end
end

Sources

• 1
• 2
• 3