Big-O notation in 5 minutes

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