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.
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
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
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
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;
}
}
}
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);
}
}
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";
}
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]);
}
}
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;
}
}
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
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
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
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 = fun
if (this.length === 1) {
return this;
}
var subsets = [];
this.forEach(fun
var temp = [el];
subsets.push(temp.concat(this.splice(idx,1).funky_subsets()));
}.bind(this));
return subsets;
};
var subsets = [];
this.forEach(fun
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);
}
{
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);
}
{
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);
}
}
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"}