• O(1) – same amount of time regardless – adding item to end of array
  • O(n) – time directly proportional to data – linear search
  • O(n^2) – every time you loop – bubble sort
  • O Log(n) – data to search reduces 50% each time – binary search
  • O(n Log n) – same as above but we bubble sort first – quick sort

  • How good an algorithm scales, as the amount of data increases.
  • What part of the algorithm has the greatest impact on the final answer

Screen Shot 2016-12-22 at 9.34.48 AM.png

  • Has an order of n cubed

Screen Shot 2016-12-22 at 9.35.09 AM.png

Order of 1, N, N squared, and others are the most common and basic.

Order of 1 // 0(1)

  • Algorithm that is going to execute in the same amount of time, regardless of the amount of data
  • Same amount of time, no matter how big array is
  • Add item to end of an array

Screen Shot 2016-12-22 at 9.38.56 AM.png

Order of N // 0(N)

  • Time to complete is directly proportional to the amount of data
  • Linear search
  • Where you have to look at every element to find one you looking for
  • Doesn’t matter if first element you find is one you looking for
  • Big O notation always describes worst case scenario

Order of N something // O(N^2)

  • Time to complete proportional to size of data
  • Bubble sort just loops through, compares values, and swaps them if one is bigger than the other

Screen Shot 2016-12-22 at 9.40.46 AM.png

  • Bubble sort, nested iterations – hampers performance – O(N^2)
  • N order for each inner loop
  • Bad – to be avoided

Order of log N // O(Log N)

  • much more efficient
  • Binary search
  • Data decreases by ~50% each time through the algorithm
  • Fast because as N increases log N is much faster than linear N
  • N will increase faster than logN
  • base 2 because in divide and conquer we divide by 2 each iteration

Screen Shot 2016-12-22 at 9.42.20 AM.png

This is why, for example, looking up people in a phone book is O(log n). You don’t need to check every person in the phone book to find the right one; instead, you can simply divide-and-conquer, and you only need to explore a tiny fraction of the entire space before you eventually find someone’s phone number.

Of course, a bigger phone book will still take you a longer time, but it won’t grow as quickly as the proportional increase in the additional size.

O(log n): Given a person’s name, find the phone number by picking a random point about halfway through the part of the book you haven’t searched yet, then checking to see whether the person’s name is at that point. Then repeat the process about halfway through the part of the book where the person’s name lies. (This is a binary search for a person’s name.)

  • Binary search first requires a bubble sort so we can divide and conquer

Screen Shot 2016-12-22 at 9.43.57 AM.png

  • Binary search cuts the amount of data to search through in half each time

O(n Log N)

  • When sorting O(N) is always the minimum because we need to look at every element at least once
  • What we want to avoid is something inefficient like O(N^2) – bubble sort
  • Quick sort is much more efficient
    • Compares values without shifting
    • Values are only compared once
    • Each comparison reduces the final sort list in ½
    • In other words the number of comparisons will be

Screen Shot 2016-12-22 at 9.45.30 AM.png

  • That’s where n log n comes from – log n!

Screen Shot 2016-12-22 at 9.45.01 AM.png

  • Recursion!