today we're gonna learn about Big O notation so

what is it Big O notation is simplified analysis of an algorithms efficiency we cover a lot of

algorithms on this channel and we need a way to compare them and some idea of how long we'll take

to run Big O gives us an algorithms complexity in terms of the input size n it gives us a way to

abstract the efficiency of our algorithms or code from the machines they run on we don't

care about the stats of the machine rather we examine the basic computer steps of the code

we can use Big O to analyze both time and space there are a couple ways to look at an algorithms

efficiency we can examine worst-case best-case an average case when we're talking Big O notation

we typically look at worst case this isn't to say the others are unimportant however let's talk

about a few rules first big o-notation ignores constants for example if you have a function that

is a running time of 5n we say that it runs on the order of Big O of n this is because as n gets

large the 5 no longer matters in the same way as n grows certain terms that dominate others here's

a list but I'll show you a visual on the next page we ignore a drop low order terms when

they're dominated by high order ones take a minute and study this chart it

can be found on Big O cheat cheat com along with a handy guide on the Big

O of various important algorithms let's run a few examples so you can see what I

mean by basic computer steps we'll start with constant time imagine we had the following line of

code this basic computer statement computes x and notice it does not depend on the input size in any

way we say this is Big O of one or constant time what happens when we have a sequence of

statements notice that all these are constant time how do we compute Big O for this block of code

we simply add each of their times and we get 3 multiplied by Big O of 1 but remember we

drop constants so it's still big o of 1 let's look at linear time suppose

we have the following for loop that prints the numbers 0 to n we know

the print statement is Big O of 1 this means the block of code is n times

Big O of 1 in other words Big O of N here's another sequence the first line we note

again is Big O of one and the for loop is Big O of n the total time is the summation of these

two but remember we drop low order terms when n gets large the time it takes to compute Y is

meaningless as the for loop dominates the run time finally let's look at quadratic time I think you can see that the print statement will be executed n times n which

gives us Big O of N squared let's do two more examples covering everything we've talked about say we have

the following block of code what is his total runtime well

we know the runtime for each of these so the total runtime

is simply the max of the three the nested for loop dominates

here so we get Big O of N squared how about this if else statement pretend the sequence of statements in each clause

have already been deduced to the big oath shown we talked earlier that when we're discussing

Big O we usually look at worst case scenario so for this situation we choose the largest

run time which happens to be Big O of N squared I hope this gives you an understanding of Big

O notation let's wrap up by talking about the real world when you're coding your algorithm

please realize that constants absolutely do matter a lot of situations have small input

sizes so a constant of two or three could have a large impact lastly for the same

reason be cognizant of best and average case depending on your application this

may be more applicable for your algorithm as always thank you for watching

please subscribe if this helped you