Javascript - Algorithm

Posted on |

Introduction

Algorithem is a step by step process to how to solve a program. Algorithm is important because it can influence the speed and efficency of our program. As our program size grow or our users grow, we don’t want slow functions affect our user experience.

Here a sneak peak of some algorithm methods that I’ll go over in further blog series.

  • Binary Search
  • Fibonacci & Memoized Fibonacci
  • Merge Sort & bubble sort
  • Caesar Cipher
  • Sieve of Eratosthenes

Big O

Lastly I want to talk about Big O notation (or Big O for short). Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. (source, Wiki). Basically Big O will tell us how scalable a function is?

There are 4 types of Big O and here are some examples

Big O Chart

Big O - O (1) - Constant Runtime

1
2
3
4
5
6
7
8
9
// Big O - O (1) - Constant Runtime
function log(array) {
  console.log(array[0])
  console.log(array[1])
}
log ([1,2,3,4])
log ([1,2,3,4,5,6,7,8])

The above example is a constant run time example or sometimes refer as O(1). This means as input size increases on X-axis, the time it takes to run never changes. (Refer to chart Above)

Big O - O (n) - Linear Runtime

1
2
3
4
5
6
7
8
9
10
// Big O - O (n) - Linear Runtime
function logAll(array) {
  for (var i = 0, i < array.length; i++) {
    console.log(array[i])
  }
}
logAll ([1,2,3,4])
logAll ([1,2,3,4,5,6,7,8])

The above example is a linear runtime example or sometimes refer as O(n). This means as input size increases on X-axis, the time will take to run increase linearly.(Refer to chart Above)

Big O - O (n^2) - Exponential Runtime

1
2
3
4
5
6
7
8
9
10
11
12
13
// Big O - O (n^2) - Exponential Runtime
function addAndLog(array) {
  for (var i = 0, i < array.length; i++) {
    for (var j = 0, j < array.length; j++){
      console.log(array[i] + array[j])
    }
  }
}
addAndLog (['A','B','C']) // 9 pairs output
addAndLog (['A','B','C', 'D']) // 16 pairs output
addAndLog (['A','B','C', 'D', 'E']) // 25 pairs output

The above example is a exponential runtime example or sometimes refer as O(n^2). This means as input size increases on X-axis, the time will take to run increase exponentially.(Refer to chart Above)

We want to stay away from these functions because they are slow and inefficent. They will slow down your application when user grows.

Big O - O (log n) - Logarithmic Runtime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Big O - O (log n) - Logarithmic Runtime
function binarySearch(array, key) {
  var low = 0;
  var high = array.lengh - 1;
  var mid;
  var element;
  while (low <= high) {
    mid = Math.floor((low + high)/ 2, 10)
    element = array[mid]
    if (element < key) {
      low = mid + 1;
    } else if (element > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1
}

Binary search takes a list (array) and a key. The array must be sorted in some way (numerically or alphabetically). This method is fast and as the input size grow our execution time will only grow logarithmicly(refer to chart above).

An example of this is looking for a word in dictionary. If we want to look for the word, “House”, we flip to the middle of the dictionary and see how close we are to letter “H”, and we ignore the 2nd half of the dictionary. We keep repeating this process until we are at letter “H”.

A search through 4,000 elements will take 12 operations, and 8000 elements will take 13 operations.

Resources