Get startedGet started for free

Understanding Big O Notation

1. Understanding Big O Notation

Let's learn about Big O Notation, a tool used to describe the complexity of algorithms.

2. Big O Notation

Big O Notation measures the worst-case complexity of an algorithm. It considers time complexity, the time taken by an algorithm to run completely, and space complexity, the extra memory space required by an algorithm. Big O Notation doesn't use seconds to measure time or bytes to measure space because results can differ based on computer hardware. Instead, we use mathematical expressions like those shown. In this video, we focus on time complexity.

3. Big O Notation

The mathematical expressions seen earlier can be plotted as shown. We see how an increase in the input size of an algorithm increases the number of executed operations. For algorithms with a complexity of O of one, the number of operations remains constant even if input size changes. We can also say it has constant time. O of n follows a linear path. The number of operations increases proportionally with increase in input. O of log n has logarithmic time complexity. O of n-squared is called quadratic time, and O of n cube, cubic time. The number of operations in these algorithms increases by a lot when we increase input.

4. $O(1)$

Here's an O of one algorithm. Our input, colors, has four elements. The constant function performs just one operation, printing the third value of the list,

5. $O(1)$

even if we increase the input by adding more colors.

6. $O(n)$

This other example shows an O of n algorithm. The loop shown iterates over the list and prints one color on each iteration.

7. $O(n)$

If we have four elements, that is, when n is four, we perform four print operations.

8. $O(n)$

If we have seven elements, we perform seven operations. If we have 100 elements, we perform 100 operations, and so on. This algorithm follows a linear pattern, and its complexity is O of n.

9. $O(n^2)$

Let's explain O of n-squared. This function contains a nested loop. We start a new loop for each element of the list, printing the current color from the first loop and the current color from the second loop. If n is three, we perform nine print operations. If n is 100, we perform 10000 operations, and so on. This algorithm follows a quadratic pattern and has a complexity of O of n-squared.

10. $O(n^3)$

Similarly, an algorithm with three nested loops that iterate over the elements of the input, such as the one shown, follows a cubic pattern and has O of n cube complexity.

11. Calculating Big O Notation

Let's calculate the complexity of this algorithm.

12. Calculating Big O Notation

The two first lines will be O of one. Inside the function, we also have O of one for the count assignment and O of n for each operation inside the first loop. As the next loop uses a different input than the previous loop, we use "m" instead of "n", where "m" is the number of items in the other_colors list. The last line of the function is O of one. If we calculate everything, we have O of four

13. Calculating Big O Notation

plus two times n

14. Calculating Big O Notation

plus two times m. We will need to simplify this expression by applying some rules.

15. Simplifying Big O Notation

The first rule is to remove the constants, so our expression will remain like this. The second rule is to consider different variables for different inputs. That is what we already did by considering n and m. The third rule says that we need to remove the smaller terms, that is, keep the term that increases faster. For example, if we had this complexity,

16. Simplifying Big O Notation

it would be simplified as shown.

17. Let's practice!

Let's practice!