Algorithms Worksheet - Big O - November 2016 Cohort

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)

O(N)

O(N+M)

O(NM)

O(log (N) log(M))

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.

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)

Algorithms Worksheet - Big O - November 2016 Cohort

More Quizzes