Big-O notation

• Notation that tells how fast an algorithm is.

• When you need to choose an algorithm, there are always trade-offs. E.g. you need a search algorithm that is both fast and correct (on its’ implementation). “simple search” (going through all elements from an array) is simple to implement and hard to have bugs - but it takes too much time to run the bigger the array. Although “binary search” is a little harder to implement and may have bugs on the implementation, it takes much less time to run if the array is bigger.

• Run times for binary search and simple search don’t grow at the same rate. With more items to search into, binary search will only take a little more time to run. Otherwise, simple search will take a lot more. As the list of numbers gets bigger, binary search becomes A LOT faster than simple search.

• Too choose wisely between algorithms, you have to know 2 things:

  • How long an algorithm takes to run
  • How the running time increases as the list size increases Big-O notation helps with that.

• Big-O notation doesn’t tell you the speed in seconds, but in the number of operations - in the worst case scenario - the maximum number of operations to find an element.

• Big-O notation examples:

  • simple search: O₍n₎ - for a list with n elements, it will take “n” operations
  • binary search: O₍log n₎ - for a list with n elements, it will take “log n” operations

• “Traveling salesperson” is a problem where you have a salesperson that needs to go e.g. to 5 cities, traveling the minimum distance. That is an algorithm that takes O₍n!₎ time - the slowest possible. It is one of the unresolved problems in computer science.