DSA Big O
1.0.0
In these drills, you'll practice determining the big O complexity of algorithms. For each drill, we'll provide a code snippet with a function, and you'll work out the big O complexity by analyzing the code without running it.
Determine the Big O for the following algorithm: You are sitting in a room with 15 people. You want to find a playmate for your dog, preferably of the same breed. So you want to know if anyone out of the 15 people have the same breed as your dog. You stand up and yell out, who here has a golden retriever and would like to be a playdate for my golden. Someone yells - "I do, be happy to bring him over"
Determine the Big O for the following algorithm: You are sitting in a room with 15 people. You want to find a playmate for your dog who is of the same breed. So you want to know if anyone out of the 15 people have the same breed as your dog. You start with the first person and ask him if he has a golden retriever. He says no, then you ask the next person, and the next, and the next until you find someone who has a golden or there is no one else to ask.
What is the Big O of the following algorithm? Explain your answer
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
What is the Big O of the following algorithm? Explain your answer
for (let i = 0; i < arr1.length; i++) {
const el1 = arr1[i];
for (let j = 0; j < arr2.length; j++) {
const el2 = arr2[j];
if (el1 === el2) return true;
}
}
return false;
}
What is the Big O of the following algorithm? Explain your answer
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
What is the Big O of the following algorithm? Explain your answer
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
What is the Big O of the following algorithm? Explain your answer
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
What does the following algorithm do? What is its runtime complexity? Explain your answer
let result = [];
for (let i = 1; i <= num; i++) {
if (i === 1) {
result.push(0);
}
else if (i === 2) {
result.push(1);
}
else {
result.push(result[i - 2] + result[i - 3]);
}
}
return result;
}
In this example, we return to the problem of searching using a more sophisticated approach than in naive search, above. Assume that the input array is always sorted. What is the Big O of the following algorithm? Explain your answer
let minIndex = 0;
let maxIndex = array.length - 1;
let currentIndex;
let currentElement;
while (minIndex <= maxIndex) {
currentIndex = Math.floor((minIndex + maxIndex) / 2);
currentElement = array[currentIndex];
if (currentElement < item) {
minIndex = currentIndex + 1;
}
else if (currentElement > item) {
maxIndex = currentIndex - 1;
}
else {
return currentIndex;
}
}
return -1;
}
What is the Big O of the following algorithm? Explain your answer
return arr[Math.floor(Math.random() * arr.length)];
}
What does the following algorithm do? What is the Big O of the following algorithm? Explain your answer
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
The Tower of Hanoi is a very famous mathematical puzzle (some call it game!). This is how it goes:
There are three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest disk at the top (making a conical shape). The other two rods are empty to begin with.
The goal of the puzzle is to move the entire stack of rods to another rod (can't be the original rod where it was stacked before) where it will be stacked in the ascending order as well. This should be done obeying the following rules:
Your Task:
Solve the drills JS File 12 iteratively instead of recursively.
Take the solutions from this repo and identify the time complexities (big O) of each of them.
Take your solutions from the iterative exercises drills in JS File 12 and identify the time complexities (big O) of each of them.
