What is Big O Notation, and Why You Should Care

[00:00] So today we're going to be looking at big O notation and time complexity. a large amount of data that you understand how your application is going to scale.

[00:13] Big O notation gives us a really simple way to understand how many operations Now, there's a few different, big o notations that you're likely to come across, but the main ones are constant,

[00:26] logarithmic, linear, quadratic, exponential, and factorial. see how the number of operations that need to be performed increases Now you can see with quadratic, exponential, and factorial

[00:41] that the number of operations rapidly increases the more elements And because the number of operations is rapidly increasing, the time it's Now we're going to have a look

[00:53] Now, the first one we're going to look at Now, constant is anything that isn't going to change So if there's a particular part of your code

[01:09] then that is considered constant. no matter how big the dataset is, but when we're calculating it, we don't really care about constants.

[01:26] we don't do O(4), we just consider that to be O(1). We're trying to get a sense overall how your application is going to perform.

[01:38] Now, the next time complexity we're going to look at is O(log n). And you can see no matter how many items that we're processing,

[01:51] to process that data doesn't increase at the same rate. Now, the typical example you see for log n is the binary search algorithm. we take a list of items and put them in size order

[02:06] We pick the middle number and see if it's bigger is bigger than we can discard the smaller half of our dataset We keep looking at the middle number and keep discarding a half

[02:22] Now, you can see with this, with each iteration, we're halving the dataset. you can get through them very quickly when you're halving the set each time. Now, as the name suggests, the number of operations

[02:37] perform is going to scale linearly with the size of the dataset. instead of using a binary search algorithm, Worst case scenario, if the number you're looking for

[02:49] then you've still got to loop through every single item in the dataset going to take N operations before your application completes. is actually the first or second number in your array.

[03:02] we're always looking for the worst case scenario. when we're calculating big O notation that we always discard static multiples. from zero to N and each one running one after another.

[03:18] because we're going through two loops, each processing N number of elements. But when we're calculating big o notation, we always drop those multiples. We just want to get an overview of how your code is performing.

[03:33] you should definitely look at trying to remove those additional loops. that are running one after the other. then that definitely does count towards the time complexity.

[03:47] So whenever you have a loop inside a loop, this is likely to be quadratic Now to see N squared in action, we can have a look at this code example. Each loop is going for one to end with the inner

[04:00] loop printing out zero on the outer loop, just printing out a new line. this is quite clearly N squared when we print out the output. and you can see when it prints out is going to give us a nice N by N square.

[04:16] to have the inner loop looping the same number of times as the outer loop index you're currently on. So in this example, we've got the outer loop going from 1 to 10,

[04:31] but the inner loop is going from 1 to i, it is only going to go up to the index So if we print this out, we can see that the number of times the inner loop is So here we can see the output is quite clear

[04:43] because it's half the size of what we had before. we always discard constant multiples, and in this case, the multiple is a half. So this still ends up being N squared when we calculate the time complexity for it.

[04:58] Now, the last one we going to look at today is the exponential time complexity, And now you can see when we look at this on a graph, that's going to be pretty bad for your application.

[05:10] It's going to have to run through lots of operations as your dataset increases and the time it takes for your application to run is going to increase as well. looking at exponential time complexity is calculating the Fibonacci sequence.

[05:23] So here we have a function to calculate the numbers in the Fibonacci sequence. So you can see here that if we put in six, we're then going to be making So first is going to be calling itself by putting in four,

[05:37] So the easiest way to picture this is by putting it into a binary tree. we're gonna have to make two calls. level we’re going to make eight calls and so on.

[05:52] we go down we’re doubling the number of calls that we need to make. statement in there. So we have if the number is less than one, then we're going to return

[06:06] So this actually puts a cap on the number of times it's going to be calling itself. down to the next level, if the number we're putting in is one or zero, then it's not going to make any further calls.

[06:20] that we could have made towards minus numbers that would have added up to But we can see here that it's never going to be two to the power N. Now, those familiar with the Fibonacci sequence will know that it's closely

[06:32] related to the golden ratio and the golden ratio is 1.618. And you can have a look on the Internet to see what they are. sequence is not 2 to the power N, but 1.618 to the power N.

[06:47] you don't want to be going through but luckily for the most common functions, it's already common knowledge as to what the big o notation is for these.

[07:02] n, and if you're doing a quicksort, that will be n log n, adding it to And if you're searching through a linked list through every single node to be able to get to the next one.

[07:18] on the eight data structures that you need to know. Thank you for watching and I'll see you in the next video.