Quiz Maker LogoMake your own QuizCopy & Edit
Make your own quizManage my QuizzesPlans / FeaturesGuides and HelpContactPrivacy & Security

Algorithms Worksheet - Big O - March 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. As above, 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. As above, 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 funky_permutations
    return [[]] if empty?
    perms = take(count - 1).funky_permutations
    perms.concat(perms.map { |perm| perms + [last] })
  end
end
O(2^N)
O(N!)
O(N^2)
O(N^N)
Array.prototype.funky_subsets = function(){
  if (this.length === 1) {
    return this;
  }
  var subsets = [];
  this.forEach(function(el, idx){
    var temp = [el];
    subsets.push(temp.concat(this.splice(idx,1).funky_subsets()));
  }.bind(this));

  return subsets;
};
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 - March 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"}

More Quizzes

Знавці України 8.0. Пікантна
1260
2020 Q3 SMMT Product Launch/Training Follow-Up Quiz
13614
What Hogwarts House Are You IN?
10515
Quine quiz travel edition- with bonus father's day round
18922
How much do you love your girlfriend?💖
1260
Cyber treats
4232
Cyber Safety!
520
Top 10 Science PYQs
1059
GENERAL FINANCE
210
فقه الصيام ٢
24120
Hello Gorgeous! You are an Empress, and your empire is your life.   But sometimes, we take hits to our self-esteem that hold us back from being as great as we know we can be.     If you’re not living with confidence, you can start by taking my quiz.  Choose the first answer that feels right as soon as you read the question. There are 40 questions and it will take about 5 minutes to complete.   When you finish, enter your email to automatically receive your results with tips on how to take your confidence to the next level. Let's begin.
39200
ž人格了解如何增進自己的競爭力
15829
Quiz Maker Logo Make your own Quiz
Powered by: Quiz Maker