Algorithms Worksheet - Big O - September 2016 Cohort

Full Name
Find the time complexity for each of the following methods. Although they were not discussed in lecture, you may assume that console.log(), printf(), and variable assignment take constant time to execute.
Find the time complexity for each of the following methods. Although they were not discussed in lecture, you may assume that console.log(), printf(), and variable assignment take constant time to execute.
def add(a, b)
  if a > b
    return a + b
  end

  a - b
end
O(1)
O(N) where N = a + b
O(N) where N = a
O(N^2) where N = (a+b)/2
def print_arr(arr)
  arr.each_with_index do |el, idx|
    break if idx == arr.length / 2 - 1
    puts el
  end

  arr.each_with_index do |el, idx|
    puts el if idx % 3 == 0
  end

  puts arr.last
end
O(1)
O(N) where N = arr[0]
O(N) where N = arr.length
O(log N) where N = arr.length
def search(arr, target)
  arr.each_with_index do |el, idx|
    return idx if el == target
  end

  nil
end
O(N) where N = arr.length
O(log N) where N = arr.length
O(N) where N = target
O(N log N) where N = arr.length
for (i = 0; I < N; i++) {
  for (j = i+1; j < N; j++) {
    console.log(i);
    if (i+5 > j-2) {
      var spooky_sum = I - j + 2;
    }
  }
}
O(N)
O(N log N)
O(N^2)
O(ij)
for (i = 0; I < N; i++) {
  for (j = 0; j < M; j++) {
    var mimble = i*j;
    var thimble = I + j;
    console.log(mimble + thimble);
  }
}
O(N+M)
O(NM)
O(M log N)
O(N^2)
var spock = "Live long and prosper";
var picard = "Engage!";

for (i = 0; I < N; i++) {
  if(i % 2 === 0) {
    console.log(spock);
  } else {
    console.log(picard);
  }
}
for (j = 0; j < M; j++) {
  var kirk = "i have nothing to say";
}
O(N)
O(N+M)
O(NM)
O(log (N) log(M))
var notes = ["do", "rei", "mi", "fa", "so", "la", "ti", "do"];

for (i = 0; I < N; i++) {
  for (j = 0; j < N; j++) {
    var position = (i+j) % 8;
    console.log(notes[position]);
  }
}
for (k = 0; k < N; k++) {
  if (k < 8) {
    console.log("A great note is " + notes[k]);
  }
}
O(N)
O(N^2)
O(N log N)
O(N^3)
var a = 1;
var b = 1;

for (i = 0; I < N; i++) {
  for (j = N; j > I; j--) {
    console.log(b);
    b += a;
  }
}
O(N^2)
O(N)
O(log N)
O(N log N)
For each of the following loops with a method call, determine the overall complexity. Assume that method f takes constant time, and that method g takes time linear in the value of its parameter.
For each of the following loops with a method call, determine the overall complexity. Assume that method f takes constant time, and that method g takes time linear in the value of its parameter.
a. for (j = 0; j < N; j++) f(j);
O(N^2)
O(j)
O(1)
O(N)
B. for (j = 0; j < N; j++) g(j);
O(1)
O(N)
O(j)
O(N^2)
C. for (j = 0; j < N; j++) g(k);
O(N)
O(k)
O(Nk)
O(N^2)
def wonky_func(arr)
  I = 1
  while(i < arr.length)
    ret_val = add(arr[i], arr[i+1]) if I < arr.length-1
    puts ret_val/100000 + ret_val * 150000
    I *= 2
  end
end
O(N)
O(N log N)
O(log N)
O(N^2)
In this problem, #search is the same #search method defined in Problem 3. Search is replicated here for your convenience:
 
def search(arr, target)
  arr.each_with_index do |el, idx|
    return idx if el == target
  end
 
  nil
end
 
Problem:

def wonky_func_deux(arr)
  I = arr.length - 1
  while(i > 0)
    search(arr, i)
    I /= 2
  end
end
O(N log N)
O(N)
O(log N)
O(N^2)
class Array
  def grab_bag
    return [[]] if empty?
    bag = take(count - 1).grab_bag
    bag.concat(bag.map { |handful| handful + [last] })
  end
end
O(2^N)
O(N!)
O(N^2)
O(N^N)
Array.prototype.mixyUppy = function(){
  if (this.length === 1) {
    return [this];
  }
 
  var mixes = [];
  var prevMixes = this.slice(1).mixyUppy();
 
  prevMixes.forEach(function(mix) {
    mix.forEach(function(el, i) {
      mixes.push(
        mix.slice(0, i).concat(this[0], mix.slice(i))
      );
    }.bind(this));
 
    mixes.push(mix.concat(this[0]));
  }.bind(this));
 
  return mixes;
};
 
O(2^N)
O(N^2)
O(N)
O(N!)
int recursiveFun2(int n)
{
  if (n <= 0)
    return 1;
  else
    return 1 + recursiveFun2(n-5);
}
O(N)
O(2^N)
O(1)
O(N!)
int recursiveFun3(int n)
{
  if (n <= 0)
    return 1;
  else
    return 1 + recursiveFun3(n/5);
}
O(N)
O(log N)
O(N log N)
O(N!)
BONUS PROBLEM

void recursiveFun4(int n, int m, int o)
{
  if (n <= 0)
  {
    printf("%d, %d\n",m, o);
  }
  else
  {
    recursiveFun4(n-1, m+1, o);
    recursiveFun4(n-1, m, o+1);
  }
}
O(N + M + O)
O(MO log N)
O(N^2)
O(2^N)
{"name":"Algorithms Worksheet - Big O - September 2016 Cohort", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Name, def add(a, b)  if a > b    return a + b  end  a - bend","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}
Powered by: Quiz Maker