Name	Name	Last commit message	Last commit date
parent directory ..
README.md	README.md

Big O Notation

Big O Notation is a way of measuring how performance of an algorithm relative to how many items you give it as input.

We measure two types of performance with Big O Notation:

Time Complexity: How long does it take an algorithm to run when given n elements as input?
Space Complexity: How much memory does an algorithm need when given n elements as input?

We usually talk much more about time complexity.

Common Time Complexities of Algorithms

Big O Runtime	Name	Example
O(1)	Constant	Print the first string in an array of length n
O(n)	Linear	Print every string in an array of length n
O(n²)	Quadratic	Print every character of every string in an array of length n (Assume that every string is also of length n)

O(1):

function constantTime(arr) {
  if (arr.length === 0) return 
  console.log(arr[0])
}

Let's assume it takes 10 ms to print a string.

arr.length (n)	Runtime
1	10 ms
10	10 ms
100	10 ms

We can see that the time it takes to run constantTime() does not vary. No matter how large n is, it will always take a constant amount of time to run our function.

O(n):

function linearTime(arr) {
  for (let elem of arr) {
    console.log(elem)
  }
}

arr.length (n)	Runtime
1	10 ms
10	100 ms
50	500 ms
1000	10,000 ms = 10 s

In this example, increasing the size of our array does increase how long it takes our function to run. Going back to our days with algebra, we can even make a math function that explains the relationship between the length and the runtime:

What is the relationship?

f(n) = 10n

What is the runtime?

O(n)

Where'd the 10 go?

Big O notation only cares about the big picture. While it can be very relevant for our code to make something 10 times faster, Big O is only used to tell you the rough area you're in.
One main reason for this is that the 10 ms figure isn't a part of our algorithm. If we used a better computer, it might only take 1 ms to print a string. Big O doesn't know what computer you're using, so it generalizes to linear time.

O(n²):

//Print out who selected which character.  Two players can select the same character.
function quadraticTime(arr) {
  for (let elemOne of arr) {
    for (let elemTwo of arr) {
	    console.log("Player One: " + elemOne + ", Player Two: " + elemTwo)
    }
  }
}

This one's a little more complicated. Let's break it down.

Our code will then print out each pair of names. Here's are a few sample inputs and outputs:

Input: ["Agnes"]

Output:

Player One: Agnes, Player Two: Agnes

Input: ["Agnes", "Bart"]

Output:

Player One: Agnes, Player Two: Agnes
Player One: Agnes, Player Two: Bart
Player One: Bart, Player Two: Agnes
Player One: Bart, Player Two: Bart

Input: ["Agnes", "Bart", "Carl"]

Output:

Player One: Agnes, Player Two: Agnes
Player One: Agnes, Player Two: Bart
Player One: Agnes, Player Two: Carl
Player One: Bart, Player Two: Agnes
Player One: Bart, Player Two: Bart
Player One: Bart, Player Two: Carl
Player One: Carl, Player Two: Agnes
Player One: Carl, Player Two: Bart
Player One: Carl, Player Two: Carl

Input: ["Agnes", "Bart", "Carl", "Duffman"]

Output:

Player One: Agnes, Player Two: Agnes
Player One: Agnes, Player Two: Bart
Player One: Agnes, Player Two: Carl
Player One: Agnes, Player Two: Duffman
Player One: Bart, Player Two: Agnes
Player One: Bart, Player Two: Bart
Player One: Bart, Player Two: Carl
Player One: Bart, Player Two: Duffman
Player One: Carl, Player Two: Agnes
Player One: Carl, Player Two: Bart
Player One: Carl, Player Two: Carl
Player One: Carl, Player Two: Duffman
Player One: Duffman, Player Two: Agnes
Player One: Duffman, Player Two: Bart
Player One: Duffman, Player Two: Carl
Player One: Duffman, Player Two: Duffman

Let's format the length of the array, number of print statements and the runtime.

arr.length (n)	Number of print statements	Runtime
1	1	10 ms
2	4	40 ms
3	9	90 ms
4	16	160 ms

What function describes the relationship between *n* and the runtime?

f(n) = 10n²

What is the runtime?

O(n²)

We can then extrapolate to fill in the same chart we were using above.

arr.length (n)	Runtime
1	10 ms
10	1000 ms = 1 s
50	25000 ms = 25 s
1000	10,000,000 ms = 2.78 hours

As the !

Let's put all the charts together:

arr.length (n)	Runtime: O(1)	Runtime: O(n)	Runtime: O(n²)
1	10 ms	10 ms	10 ms
10	10 ms	100 ms	1000 ms = 1 s
50	10 ms	500 ms	25000 ms = 25 s
1000	10 ms	10,000 ms = 10 s	10,000,000 ms = 2.78 hours

Other Runtimes

Note: log(n) means log₂(n)

We'll get to these all going forwards. Don't worry about them too much right now.

Big O Runtime	Name	Example
O( log(n) )	Logarithmic	Binary Search
O(n * log(n))	Linearithmic	Merge Sort/Quick Sort
O(2ⁿ)	Exponential	Recursive Fibonacci
O(n!)	Factorial	Generate all the permutations of a list

Ranking and Visualizing Big O Runtimes

From fastest to slowest:

O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n²) < O(2ⁿ) < O(n!)

The following graph is from http://bigocheatsheet.com:

Deriving Runtime

We just saw an example of how to derive the runtime of a function. Let's try it with some similar examples.

function exampleOne(string, targetChar) {
  for (let char of string) {
    if (char === targetChar) {
      return true
    }
  }
  return false
}

What is the runtime of exampleOne?

O(n)

Explanation:

We might need to look at each of the n characters inside str. "n" here represents str.length. The more characters we have in our string, the longer it will take to find our target character

function exampleTwo(arr) {
     for (let i = 0; i < 1000000; i++) {
     	 console.log("Many printings!")
     }
}

What is the runtime of exampleTwo?

O(1)

Explanation:

No matter how big our array is, this will always print "Many printings" 1,000,000 times. While this would take a really long time, it is always the ***same*** amount of time. It will take a constant time to run this function and it is entirely independant of the length of arr.

function exampleThree(arr) {
   let count = 0
   for (let elem of arr) {
     if (contains(arr, elem + 1)) {
       count += 1
     }
  }
  return count
}

function contains(arr, targetElem) {
  for (let elem of arr) {
    if (elem === targetElem) {
      return true
    }
  }
  return false
}

What is the runtime of exampleThree?

O(n²)

Explanation:

Our for loop goes over each of *n* numbers. Then for each of those numbers, we run contains, which will go over each of *n* numbers. We would then end up looking at *n²* numbers in total.

Worst Case, Average Case and Best Case

Usually when we talk about runtime, we talk about the Average Case runtime. This is what we would expect the algorithm to do with a typical data set. Sometimes is also makes sense to talk about the Best Case or Worst Case situation. In these cases, we can make special assumptions about the input and see what the minimum possible or maximum possible runtimes are.

Example:

function bestAverageAndWorstFunc(arr) {
    if (arr.length < 3) {
        return
    }
    if (arr[0] == 8675309) {
        return
    }
    if (arr[0] + arr[1] == 24601) {
        for (let elem of arr) {
            for (let elem of arr) {
                console.log("Gotcha!")
            }
        }
        return
    }
    for (let elem of arr) {
        console.log(elem)
    }
}

Best Case Runtime

O(1)

Worst Case Runtime

O(n²)

Average Case Runtime

O(n)

In most situations, the average case runtime and the worst case runtime are the same. But it's good to know the difference.

Examples (copied from the previous section):

function exampleOne(string, targetChar) {
  for (let char of string) {
    if (char === targetChar) {
      return true
    }
  }
  return false
}

What is the *worst case* runtime for exampleOne?

O(n)

What is the *best case* runtime for exampleOne?

O(1)

Explanation:

In the worst case situation, our target character is always at the end of the array. We would need to look at each of *n* elements before we would find it. In the best case situation, our target character is always first, so we only ever need to look at one thing.

function exampleTwo(arr) {
     for (let i = 0; i < 1000000; i++) {
     	 console.log("Many printings!")
     }
}

What is the *worst case* runtime for exampleTwo(arr:)?

O(1)

What is the *best case* runtime for exampleTwo(arr:)?

O(1)

Explanation:

This will do the same thing no matter what the input is.

function exampleThree(arr) {
   let count = 0
   for (let elem of arr) {
     if (contains(arr, elem + 1)) {
       count += 1
     }
  }
  return count
}

function contains(arr, targetElem) {
  for (let elem of arr) {
    if (elem === targetElem) {
      return true
    }
  }
  return false
}

What is the *worst case* runtime for exampleThree(arr:)?

O(n²)

What is the *best case* runtime for exampleThree(arr:)?

O(n)

Explanation:

In the worst case situation, our array looks something like [1,4,7,10,13,16]. Contains will always search the full length of the array for each element. This means that we would look at *n* elements *n* times. In the best case, our array looks something like [3,2,2,2,2,2,2]. We still need to look at every element once, but contains could stop on the first Int each time.

Compound Runtimes

So far, we've been working with functions with either a nested loop, or a single loop. What happens when we have multiple different runtimes in sequence? Let's look at an example:

function compoundRuntimes(arr) {
  for (let i = 0; i < 1000; i++) {
    console.log("Hi")
  }

	for (let num of arr) {
	  console.log(num)
  }

  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] === arr[j] && i !== j) {
        console.log("It's a match!")
      }
    }
  }
}

How long would it take to run this code?

O(1) + O(n) + O(n²)

Let's see how the runtime increases with length using our chart from above

arr.length (n)	Runtime: O(1)	Runtime: O(n)	Runtime: O(n²)	compoundRuntimes(arr:) Runtime: O(1) + O(n) + O(n²)
1	10 ms	10 ms	10 ms	30 ms
10	10 ms	100 ms	1000 ms = 1 s	1110 ms = 1.11 s
50	10 ms	500 ms	25000 ms = 25 s	25510 ms = 25.51 s
1000	10 ms	10,000 ms = 10 s	10,000,000 ms = 2.78 hours	10,010,010 ms = 2.78 hours

As the length gets bigger and bigger, the only term that matters is the O(n²) term. Therefore, we say that the runtime of compoundRuntimes(arr:) is O(n²)

When we have a compound runtime, we only keep the most significent term. In fact, the O in Big O Notation stands for "Order" because we care most about the "Biggest Order" that appears. Order in this case is talking about the order of the algebraic function also called the degree.

Compound Runtime Examples

For the examples below, give the average case runtime

Example One:

function doStuff(arr) {
  for (let num of arr) {
    for (let num of arr) {
      for (let num of arr) {
        console.log(num)
      }
    }
  }
}

What is the runtime of doStuff?

O(n³)

Example Two:

function doOtherStuff(arr) {
  for (let num of arr) {
    console.log(num)
  }
  for (let num of arr) {
    for (let num of arr) {
	    console.log(num)
    }
  }
  console.log(num)
  for (let num of arr) {
      print(num)
  }
}

What is the runtime of doOtherStuff?

O(n²)

Example Three:

function foo(arr) {
  for (let num of arr) {
    console.log(num)
  }
}

function bar(arr) {
  foo(arr)
  for (let i = 0; i < arr.length; i++) {
    foo(arr)
  }
}

What is the runtime of foo?

O(n)

What is the runtime of bar?

O(n²)

Example Four:

function secondSmallestWithSort(arr) {
  if (arr.length === 0) return
  return arr.sort((a,b) => a - b)[1]
}

What is the runtime of secondSmallestWithSort?

O(n * log(n) )

Sorting things takes n * log(n) time. We'll review why later.

Example Five:

function secondSmallest(arr) {
    let min = arr[0]
    let minIndex = 0
    for (let index = 0; index < arr.length; index++) {
      let elem = arr[index]
      if (elem < min) {
        min = elem
        minIndex = index
      }
    }
    let secondMin
    if (arr[0] === min) {
      secondMin = arr[1]
    } else {
      secondMin = arr[0]
    }
    for (let index = 0; index < arr.length; index++) {
      let elem = arr[index]
      if (elem < secondMin && index != minIndex) {
        secondMin = elem
      }
    }
     console.log(min, minIndex, secondMin)
     return secondMin
}

What is the runtime of secondSmallest?

O(n)

We have O(n) + O(n), but as n gets bigger and bigger, we only care about the highest order.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

web

web

README.md

Big O Notation

Common Time Complexities of Algorithms

O(1):

O(n):

Where'd the 10 go?

O(n²):

Other Runtimes

Ranking and Visualizing Big O Runtimes

Deriving Runtime

Worst Case, Average Case and Best Case

Compound Runtimes

Compound Runtime Examples

Example One:

Example Two:

Example Three:

Example Four:

Example Five:

Files

web

Directory actions

More options

Directory actions

More options

Latest commit

History

web

Folders and files

parent directory

README.md

Big O Notation

Common Time Complexities of Algorithms

O(1):

O(n):

Where'd the 10 go?

O(n2):

Other Runtimes

Ranking and Visualizing Big O Runtimes

Deriving Runtime

Worst Case, Average Case and Best Case

Compound Runtimes

Compound Runtime Examples

Example One:

Example Two:

Example Three:

Example Four:

Example Five:

O(n²):