Data Structures and Algorithms

Vocabulary

  • A data structure (DS) is a way of organizing data so that it can be used effectively.
  • An abstract data type (ADT) is an abstraction of a data structure which provides on the interface to which a data structure must adhere to.

Big-O Notation

Big-O Notation gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large. Theoretically, constants can be ignored.

* n is the size of the input.
  • Constant Time: O(1)
  • Logarithmic Time: O(log(n))
  • Linear Time: O(n)
  • Linearithmic Time: O(nlog(n))
  • Quadric Time: O(n2)
  • Cubic Time: O(n3)
  • Exponential Time: O(bn)
  • Factorial Time: O(n!)
  • ...
  • Finding all the subsets of a set: O(n2)
  • Finding all permutations of a string: O(n!)
  • Sorting using mergesort: O(nlog(n))
  • Iterating over all the cells in a matrix size n by m: O(mn)

let i = 0
while (i < n)
  i = i + 1
// f(n) = n
// O(f(n)) = O(n)

let i = 0
while (i < n)
  i = i + 3
// f(n) = n / 3
// O(f(n)) = O(n)

for (let i = 0; i < n; i = i + 1)
  for (let j = 0; j < n; j = j + 1)
// f(n) = n * n = n2
// O(f(n)) = O(n2)

for (let i = 0; i < n; i = i + 1)
  for (let j = i; j < n; j = j + 1)
// (n) + (n - 1) + (n - 2) + (n - 3) + … + 3 + 2 + 1
// O(n(n + 1) / 2) = O(n2 / 2 + n / 2) = O(n2)

let low = 0
let high = n - 1
while (low <= high) {
  const mid = (now + high) / 2
  if (arr[mid] === value) return mid
  if (arr[mid] < value) low = mid + 1
  else if (arr[mid] > value) high = mid - 1
}
return -1
// O(log2(n)) = O(log(n))

let n = 0
let i = 0
while (i < n) {
  let j = 0
  while (j < 3 * n)
    j = j + 1
  j = 0
  while (j < 2 * n)
    j = j + 1
  i = i + 1
}
// f(n) = n * (3n + 2n) = 5n2
// O(f(n)) = O(n2)

let n = 0
let i = 0
while (i < 3 * n) {
  let j = 10
  while (j <= 50)
    j = j + 1
  j = 0
  while (j < n * n * n)
    j = j + 2
  i = i + 1
}
// 3n * (40 + (n^3 / 2))
// 3n / 40 + 3n4 / 2
// O(f(n)) = O(n4)