Algorithm

let arr1 = [1, 2, 3, 4, 5];
let arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

/**
 * Constant Run Time
 * Big O Notation: "O(1)"
 **/
function log(arr) {
  console.log(arr[0]);
  console.log(arr[1]);
}
log(arr1); // 1, 2
log(arr2); // 1, 2

/**
 * Linear Run Time
 * Big O Notation: "O(n)"
 **/
function logAll(arr) {
  for (let item of arr) {
    console.log(item);
  }
}

logAll(arr1); // 1, 2, 3, 4, 5
logAll(arr2); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

/**
 * Exponential Run Time
 * Big O Notation: "O(n^2)"
 **/
function addAndLog(arr) {
  for (let item of arr) {
    for (let item2 of arr) {
      console.log('First', item + item2);
    }
  }
}
addAndLog(arr1); // 25 pairs logged out
addAndLog(arr2); // 100 pairs logged out

/**
 * Logarithmic Run Time
 * Big O Notation: "O (log n)"
 **/
function half(arr: number[]): number[] {
  const elements: number[] = [];

  let n = arr.length - 1;
  while (n > 0) {
    n = Math.floor(n / 2);
    elements.push(arr[n]);
  }
  return elements;
}

/**
 * Logarithmic Run Time: 隨著資料量增加，執行時間雖然會增加，但增加率會趨緩
 * Big O Notation: "O (log n)"
 **/
function binarySearch(arr, key) {
  let low = 0;
  let high = arr.length - 1;
  let mid;
  let element;

  while (low <= high) {
    mid = Math.floor((low + high) / 2, 10);
    element = arr[mid];
    if (element < key) {
      low = mid + 1;
    } else if (element > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

console.log(binarySearch(arr1, 3));
console.log(binarySearch(arr2, 3));

/**
 * Logarithmic Run Time: 
 * Big O Notation: "O (√n)"
 **/
function isPrime(n: number): boolean {
  // 關鍵在這裡的 X * x
  for (let x = 2; x * x < n; x += 1) {
    if (n % x === 0) {
      return false;
    }
  }
  return true;
}

// space complexity of foo: O(1)
function foo(n) {
  for (let i = 0; i < n.length; i++) {
    console.log('foo');
  }
}

// space complexity of bar: O(n)
function bar(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr[i] = n;
  }
  return arr;
}