2022 April 7

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.

NOTE: The original content(s) that inspired this one can be found at:
All copyright and intellectual property of each one belongs to its' original author.