Algorithms Worksheet - Big O - May 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 - May 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
Political Utopia Quiz
320
CRIMINAL JUSTICE SYSTEM QUIZ BEE 1st Year
11614
Y5 T4W3 Meanings Test
1168
PIC Part II
108540
Which Modern Artist Are You Most Like?
8416
Get to Know Me Quiz
30150
MANAGEMENT SCHEME-1
15810
Volcano Quiz
420
Virtual Coffee
12625
APEC_Questions
5230
Which D2 Exotic Hand Cannon Are You ?
11644
CRM/Insight Quiz
1050