Data Structures and Algorithms - Big O Notation

Big O notation allows us to talk formally about how the runtime of an algorithm grows as the inputs grow.

Definition:

We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases. F(n) could be,for example, linear, quadratic, constant.

Tips to Remember:

1. Arithmetic operations are constant
2. Variable assignment is constant.
3. Accessing elements in an array (by index) or object (by key) is constant
4. In a loop, the the complexity is the length of the loop times the complexity of whatever happens inside of the loop

Constant Time Complexity - O(1)

• Constant time complexity describes an algorithm that executes in the same time regardless of the size of the input data set.

Example:

function isFirstElement(el) {
  return elements[0] === el;
}

Linear Time Complexity - O(n)

• Linear time complexity describes an algorithm whose runtime depends on the value of n.

Example:

function indexOf(array, el){
  for(let i =0; i < array.length; i++) {
    if(array[i] === el){
      return i;
    }
  }
  return -1;
}

Quadratic Time Complexity - O(n^2)

• Quadratic time grows exponentially related to the number of inputs. Quadratic time is common with nested loops. The further you nest the greater the exponent (O(n^3), O(n^4) etc). You want to avoid quadratic runtime. Reference the big o graph to see how quickly runtime slows down.

Example:

function printNestedPairs(n){
  for (var i = 0; i < n; i++) {
    for (var j = 0; i < n; j++) {
      console.log('Outer loop:',i, 'Inner loop:', j);
    }
  }
}

Logarithms

• Ok, let's start off with what is a logarithm?
  • The logarithm of a number roughly measures the number of times you can divide that number by 2 before you get a value that's less than or equal to one.
    • Ex. log2(32) = 5
• Where do we see logarithmic time?
  • Searching algorithm, Sorting algorithm and some functions that use recursion .
  • I'll go into these individually in later posts.

Space Complexity

• Space Complexity: how much additional memory is needed in order to run the code in our algorithm
• In JavaScript, most primitive data types are constant space
• Strings O(n) where n is the string length
• Objects and arrays are O(n) where n is the number of keys(objects) or length of the array