Zac Anger's Blog

cs notes

12 May, 2016

notes on a bunch of stuff

Big O:

// this is `O(n)`. we go through the input(s) once, in a loop.
const crossAdd = input => {
  let answer = []
  for (let i = 0; i < input.length; i++) {
    let
      up = input[i]
    , dn = input[input.length - 1 - i]
    answer.push(up + dn)
  }
  return answer
}

// also `O(n)`.
// we assume the worst, here. and the worst is that
// the last element of `haystack` would match `needle`.
const find = (needle, haystack) => {
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle) {
      return true
    }
  }
}

// this is `O(n2)` (imagine that `2` is superscript, please).
// we have to basically go through an extra loop every time we need
// to go through one loop.. this is bad.
const makeTuples = input => {
  let answer = []
  for (let i = 0; i < input.length; i++) {
    for (let j = 0; i < input.length; j++) {
      answer.push([input[i], input[j]])
    }
  }
  return answer
}

const foo = 'stuff' // this would be called `O(1)`, meaning 'constant time'

// `O(log n)` is a good. recursion, for example, can be helpful here.
// this is tough to understand without having any real background in math
// i think what this mens is, so, `log n` means something like, what you'd need
// to raise 2 by (exponentially) to get to `n`. so if `n = 1024`, `O(n)` is like
// saying `fn(1024)`, and `O(log n)` would be like saying `fn(32)`... or something
// ... sort of? whatever, not gonna stress about it too much right this minute.

Sorts

Data Structures

Interfaces

Implementations

Some FP Basics

Submit a bug report