Big O Notation Exercises

bigONotation.js

// 1. Even or odd

function isEven(value){
  if (value % 2 == 0){
    return true;
  }
  else
    return false;
}

/*
Answer: O(1). Constant run time complexity.
Reasoning: Because you're only ever taking one value, there is no "loop" to go through. 
Even as the value gets bigger, you simply divide it by 2 and see whether it returns an integer or a float.
*/


// 2. Are You Here?

function areYouHere(arr1, arr2) {
  //let ticks1, ticks2 = 0;
    for (let i=0; i<arr1.length; i++) {
        const el1 = arr1[i];
        //ticks1++;
        for (let j=0; j<arr2.length; j++) {
            const el2 = arr2[j];
            //ticks2++;
            if (el1 === el2) return true;
        }
      //console.log(ticks1);
      //console.log(ticks2);
    }
    return false;
}

/*
Answer: O(n^2). Quadratic run time complexity.
Reasoning: For each run through the first loop, you have to run through the entire second loop.
If you add even just one more item to `arr1`, you have to run another full loop through `arr2`.
So it's quadratic because as N doubles (taking N as `arr1.length` or `arr2.length`), the time it takes
will increase exponentially (N * N).

UPDATE: As per the comments below, the above answer assumes somewhat naively that the two arrays would have the same lengths.
It's quite likely that they don't have the same lengths; therefore the complexity would be in fact O(n*m) instead of O(n^2).
*/


// 3. Doubler

function doubleArrayValues(array) {
    for (let i=0; i<array.length; i++) {
        array[i] *= 2;
    }
    return array;
}

/*
Answer: O(n). Linear run time complexity.
Reasoning: As `array.length` increases, the number of iterations increases at the same rate.
This is because you don't have to loop any more than once: however many items are in the array
is how many times you run the function.
*/


// 4. Naive Search

function naiveSearch(array, item) {
    for (let i=0; i<array.length; i++) {
        if (array[i] === item) {
            return i;
        }
    }
}

/*
Answer: O(n). Linear run time complexity.
Reasoning: Same as above with the doubler. You have to check each and every item once and only once
in order to determine whether you've got a match.
*/


// 5. Creating Pairs

function createPairs(arr) {
  //let ticks = 0;
    for (let i = 0; i < arr.length; i++) {
        for(let j = i+1; j < arr.length; j++) {
            console.log(arr[i] + ", " +  arr[j] );
            //ticks++;
        }
    }
  //console.log(ticks);
}

/* Answer: O(n^2). Quadratic run time complexity.
Reasoning: The first loop has O(n) complexity, as with each new addition, the number of times
you run through the loop increases by one. As the inner loop also has O(n) complexity, together they have 
quadratic run time complexity.
*/


// 6. Computing Fibonacci Numbers

function generateFib(num) {
  let result = [];
  //let ticks = 0;
  for (let i = 1; i <= num; i++) {
    //ticks++;
    if (i === 1) {
      result.push(0);
    }
    else if (i == 2) {
      result.push(1);
    }
    else {
      result.push(result[i - 2] + result[i - 3]);
    }
  }
  //console.log(ticks);
  return result;
}

/* Answer: O(n). Linear run time complexity.
Reasoning: As you add 1 to `num`, the run time complexity increases at the same rate. 
*/


// 7. Efficient Search

function efficientSearch(array, item) {
    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;
}

/* Answer: O(log n). Logarithmic run time complexity.
Reasoning: Cutting `array.length` in half in each iteration, the time complexity increases slowly, in a logarithmic fashion.
*/


// 8. Random element

function findRandomElement(arr) {
    return arr[Math.floor(Math.random() * arr.length)];
}

/* Answer: O(1). Constant run time complexity.
Reasoning: With no iteration occurring, selecting an element at random from an array has constant time complexity.
*/


// 9. Is It Prime?

function isPrime(n) {
    if (n < 2 || n % 1 != 0) {
        return false;
    }
    for (let i = 2; i < n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

/* Answer: O(n). Linear run time complexity.
Reasoning: Disregarding the constant time it takes to check the first if condition, this function is linear,
as it iterates through each item once and only once.
*/


// 10. Factorial of a number w/ recursion

function factorialOf(n) {
    switch (n) {
        case 0:
        case 1:
            return 1;
        default: return n * factorialOf(n - 1);
    }
}

/* Answer: O(n). Linear run time complexity.
Reasoning: This function is being called recursively n times before reaching the base case.
*/

I think // 2. Are You Here? is O(nm) where n is for array1 and m for array2
For each element of array1 we go to every element of array2
And length of array1 isn't related to array2

Thanks jhwheeler this was helpful to me~

Thanks, it's a great contribution , i needed exercises the Big(O) notation.

Glad to hear it helped you guys!

I agree with @ben8p, the exercise number #2 is O(arr1 * arr2) or O(nm) because the function has two different inputs, and their lengths could very well be different.

I agree with @ben8p , length of arr1 not the same as arr2 so will be O(n*m)

I think // 2. Are You Here? is O(nm) where n is for array1 and m for array2
For each element of array1 we go to every element of array2
And length of array1 isn't related to array2

Good point, if the two arrays have different lengths, then it would be O(n*m) complexity instead of O(n^2). Thanks for pointing this out, I'll update the gist to reflect this.

Would be nice if there were some recursive functions

@jhwheeler, please add this recursive function to the gist

// 10. Factorial of a number w/ Recursion

function factorialOf(n) {
    switch (n) {
        case 0:
        case 1:
            return 1;
        default: return n * factorialOf(n - 1);
    }
}

/* Answer: O(n). Linear run time complexity.
Reasoning: This function is being called recursively n times before reaching the base case.
*/

@jhwheeler, please add this recursive function to the gist

// 10. Factorial of a number w/ Recursion

function factorialOf(n) {
    switch (n) {
        case 0:
        case 1:
            return 1;
        default: return n * factorialOf(n - 1);
    }
}

/* Answer: O(n). Linear run time complexity.
Reasoning: This function is being called recursively n times before reaching the base case.
*/

@gitryder Done! Thank you for contributing :D

About // 2. Are You Here?
I agree that arrays inputs may be different.
But, isn't true that we analysis Big O thinking in the worst case?
The worst case would happens when both arrays have the same size.
Therefore I believe the Big O is O(n^2).

I think // 2. Are You Here? is O(nm) where n is for array1 and m for array2
For each element of array1 we go to every element of array2
And length of array1 isn't related to array2

The point is to get the worst-case scenario here. The worst-case scenario means n==m, therefore it will always be O(N^2),

This is very helpful, good compilation!

I believe in // 6. Computing Fibonacci Numbers time complexity should be O(2^n) instead of O(n).
stackoverflow - computational-complexity-of-fibonacci-sequence
youtube - Big O Notation

/* Answer: O(2^n). Exponential run time complexity. Reasoning: This function is calling approximately two copies of itself recursively n times. */

@MichalNawrot I think the solution posted is not recursive but iterative, it is using the previous Fibonacci number to calculate the next one, a much efficient solution than the ones you posted.

You can find an explanation of the differences here: https://www.youtube.com/watch?v=pqivnzmSbq4&ab_channel=mycodeschool

@juandelacruz-calvo good catch, thanks for a great link with the explanation. I should've read the code more carefully and noticed that result.push(result[i - 2] + result[i - 3]); doesn't recursively call generateFib function but rather add element to result list in linear manner.

It would be great to have here Fibonacci numbers calculated in both ways (recursive & iterative) to show the difference between O(n) & O(n^2), WDYT @jhwheeler?

Something along those lines:

// 6b. Computing Fibonacci Numbers (recursive)

function generateFibRecursive(num) {
  if(num < 2) {
        return num;
    }
    else {
        return generateFibRecursive(num - 1) + generateFibRecursive(num - 2);
    }
}

/* Answer: O(2^n). Exponential run time complexity. 
Reasoning: This function is calling approximately two copies of itself recursively n times.
*/

Having both solutions would be even better! Good idea!🙌

Thank you for the exercises! Does anyone have any good guide on how to identify algorithms that are O(log n) and O(n log n)?

Are cubic algorithms O(n^3) just three loops in one function?

I am trying to get exercises and examples of exponential algorithms O(2^n) and factorial algorithms O(n!)

Gracias capo sos un re capo ayudaste a mi y a mis CUMPAS de la UNO - Saludos cumpa! Gonza!

buenardo compi

Gracias capo sos un re capo ayudaste a mi y a mis CUMPAS de la UNO - Saludos cumpa! Gonza!

q grande gonza

Thank you, it was really helpful!

### @jhwheeler I think in Question #2, the time complexity will be O(n^2) still.

Because, even if the two arrays have different lengths, the time complexity of the areYouHere function would still be O(n^2) because the nested loops iterate through all possible pairs of elements in the two arrays, with n and m representing the lengths of the arrays, respectively. The fact that the arrays have different lengths doesn't change the fact that every element in arr1 is compared with every element in arr2. Therefore, the time complexity would still be quadratic, which is O(n^2).

@jhwheeler Good point, if the two arrays have different lengths, then it would be O(n*m) complexity instead of O(n^2). Thanks for pointing this out, I'll update the gist to reflect this.

I think in Question #2, the time complexity will be O(n^2) still.

Because, even if the two arrays have different lengths, the time complexity of the areYouHere function would still be O(n^2) because the nested loops iterate through all possible pairs of elements in the two arrays, with n and m representing the lengths of the arrays, respectively. The fact that the arrays have different lengths doesn't change the fact that every element in arr1 is compared with every element in arr2. Therefore, the time complexity would still be quadratic, which is O(n^2).

@jhwheeler Good point, if the two arrays have different lengths, then it would be O(n*m) complexity instead of O(n^2). Thanks for pointing this out, I'll update the gist to reflect this.

@Muneeb552-star
I think in Question #2, the time complexity will be O(n^2) still.

Because, even if the two arrays have different lengths, the time complexity of the areYouHere function would still be O(n^2) because the nested loops iterate through all possible pairs of elements in the two arrays, with n and m representing the lengths of the arrays, respectively. The fact that the arrays have different lengths doesn't change the fact that every element in arr1 is compared with every element in arr2. Therefore, the time complexity would still be quadratic, which is O(n^2).

It is not right as the worst-case scenario the function can get is iterating N*M times. If you have N = 3, M = 10, you will iterate 30 times but O(N^2) means that the maximum number of iterations you can, and you may, reach is 9 iterations.