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!