Big_O_solutions.md

Solutions to these problems

Note that there are other ways to solve these problems, different algorithms to achieve the same goals, which may have different algorithmic complexities.

Exercise 1:

Write a program that determines if an input is even or odd. Explain its average and worst run time

function is_odd(n) {
    return (n % 2) != 0;
}

Regardless of the input, this takes the exact same amount of time and memory to complete. It is O(1) and has identical best, average, and worst cases.

Exercise 2:

Write a program that doubles every value in an array. Explain its average and worst run time

function double_values(arr) {
    for (var i = 0; i < arr.length; ++i)
        arr[i] *= 2;
}

The more elements in the array, the longer this will take, on a perfectly simple basis - twice as many items takes twice as long. This is O(n), and has identical best, average, and worst cases.

Exercise 3:

Write an algorithm to find an element randomly in the given array. Explain its average and worst run time

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

Aside from considerations outside the control of the algorithm, this will always take the same amount of time, regardless of the length of the array. O(1) with identical best/avg/worst cases.

Exercise 4:

Write an algorithm that creates pairs that you can work with every day. Each pair be only printed once and you can't pair with yourself. Explain your algorithm's average and worst run time

function createPairs (arr) {
for (var i = 0; i < arr.length; i++) {
    for(var j = i+1; j < arr.length; j++) {
        // Print pairs containing people[i] that haven't been printed yet.
        console.log(arr[i] + ", " +  arr[j] );
    }
  }
}

Exercise 5:

Write an algorithm to determine if a given number is prime or not. Explain its average and worst run time

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

Average run time is O(n), worst case run time is also O(n) (and about twice as long). Best case is O(1); even numbers will be detected equally quickly regardless of magnitude.

There are many optimizations which can be done to this algorithm.

Exercise 6 :

Given two arrays, write an algorithm to determine whether values from the first array is present in the second array.

function any_pairs(arr1, arr2) {
    for (var el1 of arr1) {
        for (var el2 of arr2) {
            if (el1 == el2) return true;
        }
    }
    return false;
}

Average O(n^2), worst O(n^2) (if there are no duplicates, everything must be checked). Best O(1), if the heads of both arrays are the same.

Again, this can be dramatically optimized, including reducing it to O(n) in average and worst cases.

Exercise 7 :

Write an algorithm that finds the element with the minimum value in an array. Explain its average and worst run time.

function find_minimum(arr) {
    if (!arr.length) return null;
    let x = arr[0];
    for (let el of arr) if (el < x) x = el;
    return x;
}

Regardless of the input, this will iterate exactly once through the array. Best, average, and worst cases are all O(n).

Exercise 4:

var people = ["JP", "Dennell", "Benjamin", "Paul", "Donna", "Emily"];
var i, j;

function createPairs (arr){
for(i = 0; i < arr.length; i++){
    for(j = i+1; j < arr.length; j++){
    // Print pairs containing people[i] that haven't been printed yet.
        console.log(arr[i] + ", " +  arr[j] );
    }
  }
}

createPairs(people);