Algorithmic Efficiency Hacks: Javascript

Let’s test your knowledge on algorithmic efficiency!

Hack 1: How Much Time?

Objective: write the time complexity of the algorithm below using Big-O notation.

(don’t worry about special cases such as n = 1 or n = 0).

%%javascript
let n = 5; // change this value to test different outputs!

for (let i = 0; i < n * 2; i++) {
    console.log(i);
}
console.log(O(n))let n = 5; // change this value to test different outputs!

for (let i = 0; i < n * 2; i++) {
    console.log(i);
}

// Print the time complexity
console.log("O(n)");

//TODO: print the above algorithm's time complexity
//BE CAREFUL - This one might trick some people. Remember that Big-O notation shows how much an algorithm's time complexity GROWS, so coefficients don't matter...

<IPython.core.display.Javascript object>

Hack 2: Your Turn!

Objective: write an algorithm with O(n^2) time complexity.

%%javascript
const n = 10; // change this if you want

for (let i = 0; i < n; i++) {       // Outer loop
    for (let j = 0; j < n; j++) {   // Inner loop
        console.log(i, j);
    }
}

// Print the time complexity
console.log("O(n^2)");

<IPython.core.display.Javascript object>

Hack 3: Gotta Go Fast!

Objective: Optimize this algorithm so that it has a lower time complexity without modifying the outer loop

%%javascript
const n = 10; // change this
let count = 0;

for (let i = 0; i < n; i++) { // Outer loop, DO NOT MODIFY
    count += i; // Instead of looping j from 0 to i-1
}

console.log(count);

<IPython.core.display.Javascript object>

Hack 4: Extra Challenge

Objective: Write an algorithm that does NOT have a time complexity of O(1), O(n), or O(n^x) and identify the time complexity

(I will not accept O(n^3) or some other power, it needs to be more complex.)
%%javascript
const n = 5; // change this number

let count = 0;

// Double nested loop with doubling behavior (exponential), confused me and took me quite some time!
for (let i = 0; i < Math.pow(2, n); i++) {
    count++;
}

console.log("Count:", count);
console.log("Time complexity: O(2^n)");

<IPython.core.display.Javascript object>