jharris-code

//Time Complexity: Worst: O(N^2) - if pivot point is most extreme, and array is already fully sorted, 
//then complexity of partition will be N, then N - 1, then N - 2, etc. Sum up all the N's and this results in N^2
//Average/Best case: O(N Log N) - if pivot point is at the middle then N + (N/2) + (N/4) + (N/8)... = N * (Log N)
//Space Complexity: O(log N) - array is sorted in place, however, stack frames result in Log N recursive calls

let arr = [5,1,9,10,15,7,7,12];

//Time Complexity O(N)
const partition = (low, high) => {

jharris-code

//Time Complexity: O(N log N) - mergeSort is called Log N times, each merge iterates over N elements, so N*(Log N)
//Space Complexity: O(N) - the depth of the call stack is Log N, and each recursive call contains a N/2 copy of the array.
//If you sum up each sub array in the call stack this would be N/2 + N/4 + N/8 + 1 which equals N. 
//If new sub arrays were NOT created in each call, then space requirement would be only for the stack frames, which would be Log N.
const mergeSort = (a) => {
  if(a.length === 1) {
    return a;
  }
  let middle = parseInt(a.length / 2);
  let end = a.length;

jharris-code

//Assumes: 
//a Queue data structure is available with push(), pop(), isEmpty() methods.
//each node in the Queue have left and right properties.

//Time Complexity: O(N)
//Space Complexity: O(N)
const bfs = (root, value) => {
  let q = new Queue();
  
  q.push(root);

jharris-code

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

//Time Complexity: O(N) since we traverse every node worst case
//Space Complexity: O(H) height of tree is number of stack frames in memory

jharris-code

function binarySearch(nums, target) {
  let start = 0;
  let end = nums.length - 1;
  let p;
  
  while(start <= end) {
    p = Math.floor((start + end) / 2);
    
    if(nums[p] === target) {
      return p;

jharris-code

function bubbleSort(arr) {
  let swapped = true;
  
  while(swapped){
    swapped = false;
    
    for(let j = 0; j < arr.length - 1; j++){
      if(arr[j] > arr[j+1]){
        swapped = true;