Algorithms Worksheet - Big O - March 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. As above, 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 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)

Algorithms Worksheet - Big O - March 2016 Cohort

More Quizzes