Big O 101 - Howdy Internal Talk

This talk describes the concept of Big O notation, which is used in software development to describe the time and space complexity of an algorithm. It considers the worst-case scenario and approximates the number of steps required to execute an algorithm based on the order of operations count. The text describes four different Big O notations, each with an example: O(1) (constant time), O(n) (linear time), O(log n) (logarithmic time), and O(n^2) (quadratic time). These examples demonstrate how the execution time of an algorithm changes with the size of the input data.

O(1)

Constant time: in theory, no matter how many elements you have to process, it will take the same amount of time to execute.

e.g., you are in an all-inclusive hotel feeling hungry, picking up snacks from the buffet

O(n)

Linear time: the execution time grows linearly with the number of elements to be processed.

e.g., same situation as before, but you want to choose what you want to eat. The bigger the buffet, the longer it will take you to find what you want.

O(log n)

The algorithm's execution time is proportional to the logarithm of the input size n.

e.g., same situation as before, but now the buffet's dishes are sorted by name. You can start in the middle, go left/right, and successively repeat the same until finding it.

O(m+n)

This is a linear time also. T=T(m)+T(n)=TTotal. As TTotal it a constant, by convention the order will be O(n).

e.g., same situation as before, but you decide to eat à la carte. Now you have to review the menu, pick something, and order; the chef will prepare each order.

O(n^2)

#Quadratic time: Its execution time is proportional to the square of its input size.

e.g., same as before, you decided to eat à la carte, but the chef doesn't like to repeat orders. Now you have to review the menu and, for each dish, check that nobody ordered the same.