Big O Notation & Time Complexity Analysis Tutorial

Key Takeaways

[Music] in this video i'm going to explain to you big o notation as well as how to perform time complex the analysis on various algorithms now i have a ton of examples and i want to make this video really focused on going through different examples and practicing performing time complexity analysis so if you're familiar with bigo notation skip forward in the video to those examples they'll be in the video player or in the description if you're unfamiliar with big o notation then stick around for the first few minutes where i give you a conceptual overview on the whiteboard now i will mention that i'm not going to be covering other time complexity analysis so we're not going to be looking at big theta big omega space complexity we are simply looking at big o notation and in a second i'm going to explain what that is now before we get into it i will mention that i do have a course it's called programming expert teaches fundamental programming object-oriented programming advanced programming tons of practice questions tons of projects you guys can check it out from the link in the description and use discount code tim with that said let's go ahead and get into the video all right so i want to begin by just discussing what big-o notation is very generally and why it's important for programmers of all types to actually understand this concept so big o notation is essentially a tool that we use to analyze different algorithms data structures and just sections of code and figure out relatively how much time they're going to take to execute based on the approximate number of operations that need to be completed in the worst case i understand that sounds a little bit confusing but the idea is we want to be able to look at two different algorithms and very quickly determine which one is going to be more efficient based on its big o notation so big o notation again is a tool we're using it to compare different solutions different algorithms different data structures the algorithm is data structures that have the best big-o notations are typically the ones that we prefer because they're going to be the most efficient they're going to take the least amount of system resources or they're at least going to execute the fastest now big-o notation is really concerned with what happens when we scale our problem to a very large size so we're not really wondering what's going to happen when we sort 5 numbers or 10 numbers we're concerned with what's going to happen when we sort a million numbers if we're comparing say different sorting algorithms or what happens when we pass the worst case scenario of numbers to be sort so big annotation worst case scenario for very large inputs that's what we're focused on okay that is a very general introduction to big o notation the reason it's important for us to understand this is because there's a lot of scenarios where we can write code that solves a problem but doesn't do it in an efficient manner and the only way we know it's not happening efficiently is if we understand relatively how many operations this code takes compared to another more optimal solution so this is our comparison method without this method you really have no way of understanding you know how long your code is going to take to execute and that means that it might work for a small input but if you pass it say a thousand numbers or ten thousand numbers or a large list of strings or whatever the input type is it may take a really really long time to execute and may even be infeasible there's a lot of algorithms that you and me have probably both written in the past where if you fed them say a million numbers they may actually take years decades hundreds of years to execute based on how inefficient they are and just the math that goes on behind the scenes here anyways we're going to start looking at a ton of examples i'm going to hop over to the whiteboard and start explaining to you kind of the theory behind big o and how we find the big-o notation of specific algorithms all right so i'm here on the whiteboard i'm going to ask you to please not be too intimidated by the math that you're already seeing it's going to be really simplified once i start going through a few examples so as i mentioned before when we're talking about big o notation to actually find the big o notation or the big o function that represents an algorithm or a data structure or whatever it is we need to first know how many operations a algorithm is going to take okay so the first step that we always do when we're analyzing something for its big o notation to try to compare it against something else is we figure out the approximate number of operations that this algorithm takes we're then going to use those to simplify and find the big o function or the big o notation okay so let's write a super simple example here let me just get clicked into this screen and we'll start going through so i'm going to say total is equal to 0 i'm going to say 4 i in n i'm going to explain what n is in a second and hello catch just decided to join me here i'm going to say total plus equals i and then i'm just going to print i okay so this is my out now the first thing to discuss here is n you're going to see this a lot n refers to the size of our input so as i mentioned before when we're talking about notation we're really concerned with what happens when we have really large inputs so n is just a placeholder to represent the size of our input and we write our big o function and the number of operations relative to n so in this case here if we're counting the number of operations that are going to occur we have one operation to define the variable we're going to have n loops that's going to happen n times because n is the size of our input right so i'm going to say n and then we have two operations happening inside of the for loop so if this for loop happens n times and we have two operations we have a total of two n operations happening in the for loop so we're going to say 2n plus 1 is the number of total operations that this algorithm is going to take because we have 1 here and then n times 2 2n hopefully that is clear so what we're going to do is we're going to write this as what's known as our f of n okay i'm going to start going through this definition in a second let me just erase this part here and move over the 2n plus 1. okay so actually we'll just rewrite it over here okay so f of n is going to be equal to 2n plus 1 and f of n is going to represent the number of operations that our algorithm takes so now let's look at this definition so this says that f n is equal to the big o of g of n so where f is big o of g you can read it that way if there exists constants capital n and c so that for all n greater than or equal to uppercase n this inequality is true now it's important to note here that c and capital n have to be at least one so one or greater uh and we'll go through this example so this makes a bit more sense so let me just write out this inequality we have f of n needs to be less than or equal to c times g of n so just to stop and explain something here g of n is the function that we're looking for which is going to be the big o function or the big o notation of f of n or of our algorithm okay g of n is really what tells us approximately how long this code is going to take to run based on the input in this case n okay so everything refers to n again we're really concerned with what happens as n gets to a very very large number so we need to find something that satisfies this inequality and we want this right hand side here to be greater than or equal to n but be as close to n as possible the reason i'm saying that is because any of you who are kind of working this out in your head already can probably realize if i substitute in 2n plus 1 for f of n here and i say less than or equal to c times you can pick some very very massive function maybe something like n to the exponent 4 and well this is going to be true doesn't actually matter what value i pick for c it doesn't matter what value i pick for uppercase n this is always going to be true so i don't want to just pick an arbitrarily large function i want to find a function that's as close as possible to this one right here that still makes this true okay again i know this is confusing we're going to keep going through it there's just a lot to get through before you can really even look at an example so number of operations is 2n plus 1. we have f of 1 f of n is less than or equal to c times g of n and that's going to be for all values n that are greater than uppercase n so there's kind of two things that we need to pick here now let me just try to erase this okay so let's now write the inequality again 2n plus 1 less than or equal to c times g of n and this is 4 n greater than or equal to uppercase n so there's three things that we need to find to prove this true now what i'm going to do is just randomly pick a function for g of n and show you how this works so i'm going to say 2n plus 1 is less than or equal to c times and then the function i'm going to pick for g of n is simply n okay just the regular linear function i'm picking n so now that we have this and again this is going to be for here i'm not going to rewrite that we need to find some c that makes this true and if we find some c that does make it true as well as some uppercase n then we know that this is kind of our big o function that's what i'm going to be calling it all right so for c we can find this pretty easily we can just pick a very large number right i can pick a number like 10 i can pick a number like even 3 here that'll make it true essentially anything other than 2 or 1 is going to make this true and remember c has a minimum value of 1. so if i pick c equals 3 then that gives me the inequality 2n plus 1 is less than or equal to 3n okay great and then i need to just find some value uppercase n where all n values past that or equal to it make this true and really i can actually pick the value 1 for this and it will make this true right so if i pick this so n is equal to 1 then we can just plug in 1 and we'll see that this is always going to be true so when i plug this in i get 3 less than or equal to 3 so that's if 1 is 4n and if i were to plug in 2 3 4 5 so on and so forth you're going to see that this side here is always going to be less than or equal to or sorry greater than or equal to this now what does that mean that means that g of n is the big o notation of f n so i can say f n is equal to the big o of n and that's how you write this say f of n is equal to big o of n or the algorithm has a time complexity of big o of n okay again i know this is confusing but i've just showed you very very quickly how we kind of use this mathematical definition to find a g of n now what does g of n really mean well g of n means that as the input increases the amount of time that our function takes to execute increases linearly okay increases on a straight line as n increases in a linear function way the amount of operations increase so if n is one we have one operation if n is two we have two operations it's not telling us the exact number of operations because we know that's two n plus one it's telling us relatively what happens to the amount of time it takes for us to execute when the input value for the function gets increasingly large that's the point hopefully this is coming across that's what we're doing with big o of n here so yes big o of n is actually less than two n plus one that's fine we don't care about the exact number of operations we care what happens to the amount of time it takes when the input increases and now that we have this function n we know that it increases linearly the amount of time so let's clear all of this and let's just go through one more example here and look at some of the big-o functions which you can see on kind of the right-hand side of my screen okay so let's say we have a function here that is something like two n squared plus n plus one okay this is the amount of operations that it takes we'll say this is f of n should have wrote it in the other way but that's fine now i'm going to write the rest of this in black here uh just so you're aware okay so now we want to find g of n for this so what do we do well we're going to write this out 2n squared plus n plus 1 is less than or equal to c times g of n for n greater than or equal to n okay so now let's pick something for n or pick something for g of answer so 2 n squared plus n plus 1 less than or equal to c times what if we pick n now if we pick n immediately we're going to see here that it doesn't actually matter what constant we give even if we give a constant like a thousand when i start passing really really large values for n n squared is going to exceed c times n very quickly right so if i pass even a huge value for n uh like you know a thousand ten thousand you're gonna see that this side here is gonna be a lot greater than this side here even though i'm multiplying it by a thousand now that's not something you're necessarily gonna prove but you just need to be able to look at that and kind of figure that out when i have an n squared and i have an n over here doesn't matter what the constant is this is always going to outgrow this side eventually when we get to a very large number of n so that tells me that i cannot find some c and i cannot find some n and so n is not going to be a valid function for g of n so now instead let's try n squared so now if i have n squared i'm actually going to be able to prove that i can find some constant c so to prove this again i just need to find some c and i need to find some n so let's look for a number for c let's just pick a thousand okay so if i say c is equal to a thousand now we can plug this in so we're gonna say a thousand n squared and i don't know why i'm writing these in different colors but i just am i'm gonna say two n squared plus n plus one now it actually doesn't really matter what value i pick for uppercase n here in fact i can pick any value and you're gonna see that we get uh the correct inequality here okay because i've picked a large enough number for c now you can make a smaller number of receipt it doesn't matter what number you're picking you're just picking that to prove that this inequality is true so for example if we plug in say one right we have two one plus one plus one that's going to give us four and then this right is going to give us a thousand so this is larger if we pick 2 this is going to give us 4 000 this is going to be a much smaller number so you're going to see that this side is going to be greater so there we go we now know that the function here is going to be n squared so what we can do is we can write f of n is equal to big o of n squared now you might start be starting to realize a pattern here and the pattern is you can essentially look at the largest term when you have things being multiplied together and understand that that is going to be what the big o function is now there's a few tricks and i have to go through a bunch of them but the point is here when we have something like 2n squared plus n plus 1 if my function g of n is simply n squared i'm going to be able to find a large enough constant that it doesn't matter what the other terms are here it's always going to be greater than this so let me just stop here for one second go through this example again and make sure it's clear because i get this is confusing and this is something that you have to look at a bunch of times before really starts to actually make any sense so i have 2n squared plus n plus 1 that's the number of operations that my algorithm takes now i'm trying to find a simplified function that is going to give me a general concept of what happens to the amount of time or the amount of operations required from this algorithm as the input grows very very very large so again we're thinking of really large values of n so when the values of n grow really large what's going to happen is this term right here is going to be dictating the number of operations that are occurring if you pick a value even something simple like 10 right the 2 times n squared gives you 200 the n gives you 10 and the 1 gives you 1. so these become increasingly less important the n plus 1 as n squared gets larger and larger and the same thing happens with this 2 here this becomes increasingly less important as n squared gets larger and larger and larger right that's really the point here as n gets larger all of the constants that we have here n 1 and 2 are going to become less important now the n is not a constant i know but it still becomes less important because n squared is much much larger than n that's what we're looking at so what we do is we get the bigger notation of n squared because this is the term that most accurately represents what happens to the amount of output or i guess the time to execute our function as the input increases and again the way we did that is we're using the math here to prove this i'm going to show you a bunch of shortcuts so you don't have to do this math every time but it's important just to see kind of how this works so you understand the math that goes behind this and how you prove you know that your bigger notation is actually correct okay so now let's just look at a few more functions and we're going to do them in a really fast way and i'm going to show you a few shortcuts that are going to make this seem really easy so let's say we have f of n is equal to 3 and let's go with n cubed plus n squared plus and then we're going to go uh oops let's go like this log base 2 of n okay so notice these are all pluses right so i have 3n squared plus n squared plus log base 2 of n now a few shortcuts that you can keep in mind here is whenever you have terms that are being added together so additive terms you can essentially cross out and remove every single term and constant that is not the largest term that you have in the expression so again the reason that you can do this is because as n increases and reaches infinity n cubed is going to dictate the amount of operations that this is going to take let's just plug in a value and have a look at it right all right so let's just plug in 10 here and see what we get so we're gonna have i guess three times a thousand plus this is going to be a hundred plus approximately six point six so if we look at this we're gonna see these terms right even the three become increasingly less important as n gets large and n isn't even that large n is ten imagine what happens now when n is ten thousand ten million the n cubed really carries the number of operations and so we don't care about these ones right here and we can cross them off when it comes to our big-o notation now to be able to actually cross these off you can do a bit of math to kind of prove that you can cross them off so what i'm going to say here is let's assume that n squared and log base 2 of n is equal to n cubed so the reason i can assume that is because n cubed is greater than n squared let's assume that n squared is equal to n cubed now i know this is not sound math but just assume that n squared is equal to n cubed if it is then what i can do is change all my n squared terms to n cubed so if i change n squared here 2n cubed which is larger than it so it's vowel for me to do that because i'm adding something in that's larger than n squared and i change my log base 2 of n to the same thing n cubed what you see here is we end up now if we factor this we get 5 n cubed now again the 5 is a constant we don't care about the constant because we don't need to know the exact number of operations we just want to have the function that tells us what happens as the input gets larger so n cubed is that function so we simply strip off the 5 and we say that the bigger notation here is n cubed that's the way that we do this so if you take every single other term that you're adding it's very important that you realize we're adding these terms here and you say okay well if it's smaller than n cubed let's assume it's n cubed now if we add all of these together and not factor so i said factor four if you add all of them together we get 5n cubed we know we don't care about the constants because we're just looking for a function to give us the relative amount of operations then what we can do is cross off the constant which would have been 5 and we're left with n cubed okay so that's one example let's now look at another example that has to do with multiplying terms so let's now say we have something like 3n and we're going to multiply this by the log base 2 of and then this will be n squared okay so this is actually what we have now what we want to do is simplify this and find g of n so we can find the big o notation so for this function here the first thing that we know we can do is remove the constants again we can remove them because we don't care about constant values we only care about a function based on the input that tells us what happens to the number of operations or the expected kind of running time of the algorithm based on the size of the input so we can remove the constant so we remove the constant 3 and that leaves us with n multiplied by log base 2 of n squared okay now we don't really know how to handle this n squared inside of here and i'm going to show you how we can simplify this even more you could technically say that this is the big o notation right now we can get even simpler we can take this 2 out based on using exponent rules i'm not going to derive these rules for you i assume most of you probably know this already at least if you're in high school let me write log properly we're going to be able to take the 2 out right before the log and then we can put this here now again the reason we take the 2 out is because whenever we have something to the exponent inside of a logarithm that exponent we can simply put as a multiplication to whatever the logarithm is of the base of that number and so that's what i'm doing so i'm saying 2 log base 2 of n i can take the 2 out now the 2 is what a constant we don't care about the constant so i can remove the constant okay so now if we continue i get n and then i have log base 2 of n now can i simplify this anymore no i cannot i cannot simplify because we are multiplying these terms not adding them if we were adding the terms together i could remove the log base 2 of n because it's smaller than n but i cannot in any way here find a way to actually write this as a constant multiply by n like previously if i had n plus and then i had log base 2 of n i can say that since log base 2 of n is smaller than n i can write this as n plus n that gives me 2n and then i can cross out 2 but here since we're multiplying the terms together i don't have a way to do that and so i can't simply remove the log base 2. okay if you wanted the math version of that that's why it also makes sense here since we have two factors being multiplied they both really affect how much time this is taking so we need to keep n log base 2 of n around okay now that we've looked at that let's just have a look at what's on the right-hand side of my screen and then let's get into some some examples because i'm sure a lot of you are tired of this math so on the right-hand side of my screen here we have the big-o complexity chart now let's just see if we can make this bigger so that we can take up the full screen with it nice okay so this is the chart now it actually is pretty good i don't really need to explain it too much but it simply shows you the big o functions and which ones are better than each other because once you find the big o notation that's great but you need to know which functions are better than other functions in terms of their complexity now we've already looked at log of n log of n is great that means that essentially as the input increases the number of operations we need to do is on a logarithmic basic basis which means it's getting smaller and smaller when log is equal to a hundred we have six when log is equal to uh 128 we have seven when log is equal to 256 uh we have eight right so on and so forth now i might have been messing those up a little bit you get the point as we get to a really really large number it stays really small when we have a logarithmic time complexity then we have a constant time complexity o of one this means that there's actually nothing based on the input this would be like printing a number or you know checking if a number is odd or even performing a modulus this is a constant time operation this isn't something that requires the input so if it doesn't matter to the input at all it only ever takes 100 steps or 50 steps or a thousand steps a constant number of steps then we have o1 a constant time o n this is linear this is a fair or good time complex if you have a linear time complexity usually that's pretty good it means your algorithm's time scales with the input so as the input increases the amount of operations uh increase relatively at the same amount if we have 10 inputs we have you know about 10 operations if we have 20 operations or 20 inputs we have 20 operations now it might actually be 100 operations or 200 operations but that's fine because it's happening linearly not exponentially or any of the other complexities that we're going to look at okay continuing with n log n now n log n is kind of a middle ground here as you can see we're multiplying a linear time complexity by a logarithmic so it's not horrible it's not as bad as something like n squared but it is you know fair it's going to take a long period of time if we have a lot of inputs again all of these are time estimates used to be compared against each other we're not looking at an exact amount of operations or exact amount of time so n log n fair time complexity it is better or sorry worse than a big o of n okay now we have n squared n squared is a horrible time complexity that means that we increase the number of operations we need to do exponentially as n increases and i'm sure many of you have looked at exponents before not very good when n gets to a large number say we add 10 we have n squared that gives us 100 already keeps getting larger and larger and larger then we have something like 2 to the exponent n now this is even worse this is a very very poor time conflict as you can see then we have something like n factorial and we have even more complex time complexities where we have something like n factorial multiplied by 2n plus m and would be another input i'll talk about that later but this is the general graph so you kind of need to memorize this graph it's pretty easy you could just plug in some values and actually see which ones are getting larger faster if you are unsure but these are the most important big o functions and we're going to be using combinations of these functions when we're analyzing the time complexity of the examples i'm about to go through so i apologize i know this was long but i just wanted to try to explain this as best as i could hopefully that made sense now we're going to go through 12 examples and i'm going to walk you through exactly how we solve them all right so we're moving on to the first example here example zero i'm going to ask you right now what is the time complexity or big o notation of this function think about it pause the video if you need to i'm about to go in and explain so the answer here is that this is constant time okay now i'll explain why it's constant time but this is big o of one so inside of here what we're doing is we're performing a constant number of operations it does not matter what num is and num is going to be n right num is n because that's our input so whatever the size of num is we represent that with the variable n and it doesn't matter what this is it's always going to take us approximately the same amount of time to perform this calculation right the modulus of 2 or the num modulus 2 and we're just checking if this number is odd or even that's what we're doing here so this is a constant time operation fairly straightforward now i want to mention that if i did something like x equals 1 y equals 3 whatever this is still a constant time operation i don't write something like o of 3 i just keep it at 0 1 which means we're going to do the same amount of steps no matter what n is no matter what the size of our input is and as we go through these next examples you're going to see that i've labeled inputs different values you know numbers strings whatever you still want to represent them using n n is the length of your input or the size of your input in every single situation okay so let's now go to example one example one we've seen this example kind of already i've total equal zero for number in nums total plus equals number return total pause the video what is the big o notation of this example or of this algorithm right here okay so the answer as i'm sure many of you have gotten and probably fairly quickly is big o of n now n is representing the number of numbers that we have in nums so the size of our input now what we do here to calculate this is exactly what we did in that first example that i showed you we have a variable this takes one one operation right we have a for loop this is going to take n it takes n because the number of numbers is n right so this for loop runs n times we're doing one operation so what we end up getting here at the end you could count this as an operation if you want as well is something like n plus one or n plus two whatever you want to write okay so we'll say it's n plus 1. if we have n plus 1 we know that we can simply remove the constants which are 1 because as n gets larger they're not going to matter and write the big o notation as big o of n okay so that's that example let's move forward okay now this one is getting a bit more complicated now we have an example where we have a nested for loop so again pause the video go ahead and read this and it's going to get even more complicated as we go on all right so let's go line by line we have results here and results we're creating a list now this list we have a for loop here we've got to look at all of our loops okay and any operation that could be looping and what happens is we need to 4n right so for underscore in range len of nums lenum nums really is just n we're adding 1 into the list so this is going to take us n to do because we're adding 1 n times pretty straightforward move on to the next loop okay inside of this next loop well how many times does it take for this loop to run this loop is going to take n times to run because we're doing it for the size of our input which is n okay now we have another for loop inside of this for loop now that means that this for loop needs to run how many times n times and how long does it take for the for loop to run well this for loop is looping through nums as well and so that gives us n okay so we have n stuff happening n times because this for loop is happening now inside of here we can count the operations we could say this is an operation this is an operation and this is an operation now remember we're considering the worst case so in one case when num1 is equal to num2 we're not going to perform this operation however we don't really care about that we're not going to factor that into our calculations here because this could happen right it's happening every time except once so we're just going to assume that this operation happens the end times for this for hopefully you get what i'm saying but i'm just trying to get through like don't over complicate analyzing the number of operations here we're just trying to get a rough estimate and then we can actually figure out what the big o notation is okay so we have about three operations at most we have to perform a condition we're going to continue we could count as an operation i'm going to do a multiplication we'll just sum all of those up even though they're not all going to happen together okay so we say approximately we're going to get three operations inside of here then we're returning results okay that's another operation so we have n now we're adding that because this is it not inside the for loop where it's the next line down to n okay and then how many times or how many operations are going on inside of this n well we have three n so we're going to say n and then this is just going to be multiplied by 3n now i get this a bit confusing but what's happening is this for loop is happening every single time this for loop runs so we're doing this for loop n times which means we're going to have n times n right two n's there so that's n squared and then we're doing three operations inside of this internal for loop and so what we end up getting is three n squared if we multiply these all together we're gonna get n plus three n squared and then we have one more operation here so we add one so this is going to be the you know approximate number of operations that we're doing inside of this algorithm now what do we do well we look for the largest term which is n squared we cross off all of our constants and then whenever we have a variable we say okay was this term smaller or larger than this one well it's smaller so if we assume it's n squared then we could write this as 2n squared which means i can now get rid of that and that means my big o notation is going to be n squared i know i made a complete mess here but this is going to be n squared okay that's the big o notation let me get out of this mass let's look at it here in the code edit so we perform an n operation that happens okay then we go inside of here we have an n times n operation because we're doing this for n times for this for loop which happens n times we need to multiply them together inside this for loop we're doing three things so we have three n squared that's how long all of this takes to run so we add that to n add that to one and we get 3n squared plus n plus 1. we know the other terms are smaller so we cross them off and that leaves us with the big o notation of n squared okay so big o of n to the exponent 2. let's write that there okay this is going to start to make sense as we go through more examples though that was an n-squared algorithm now we're moving on to this one so let's look at this now we have two inputs here so it gets a bit more complicated num1s and nums 2. now just like we used n to represent the size of our first input we're going to use another letter in this case m you can use whatever you want but the tradition is n and m for the second input so we have two inputs you got to consider with the length of the size of both of the inputs how long does this take n and m okay so pause the video if you need to and take a guess and i'm going to run through so again let's take a full screen snip here let's go full screen snip and let's try this okay so we have nums one nums two so for nums one can i change the pen color here actually i think red is fine we'll say this is n and we'll say that's m okay results one operation for num in nums one well nums one that's n so this is going to take how many operations are we doing just one so we can say this whole thing just takes n time okay nums two this is m right size of that input inside of here how many operations are we doing just quickly add them up doesn't need to be super precise one two three operations okay so this is going to be taking 3m time results that takes 1. let's add these all together because they're not inside of each other so we can just add them together so we're going to have 1 plus we'll add the other one down here so 1 plus n plus three m okay now we need to cross off all the constants so we get rid of one get rid of one get rid of three what does that leave us n plus m okay we cannot simplify this any further because n and m are going to be two distinct variables representing the two inputs that we have to our function so you're going to see this a lot you have multiple inputs you need to use a different variable to represent each input and then that tells you the approximate time complexity of the function so again we're going to write this as big o of n plus m now if you wanted to do this really quickly all you would do is look for the loops that involve n and m so we see we have a loop here with n see we have a loop here with m boom all we do n plus m that's all we need to look at now we can look inside of these loops and try to see if there's more looping if there's no looping and it's constant time operations which all of these are here then we don't have to consider them we just cross them off because they're constant every loop is going to take the same amount of time so we don't need to consider it it's not based on the size of the input okay so o n plus m okay let's continue to example four i got a ton of examples to keep practicing this okay so now we're doing a bunch of stuff here so let's again go to the full screen snip you guys can pause the video if you want and take a guess at what the time complexity is okay so we have example four we take in a nested list now the nested list is going to be something like this right there's going to be a list inside of another list and this can make it a bit complicated so when we're dealing with a nested list what we're going to do is assume that the list has a height and a width now we could draw this in kind of more of a square fashion but it might be something like this okay and what we would get here is this would be the height so the number of lists inside of the list and then the width would be the number of elements inside of each list and we would assume that would just be the same okay so we have height and width and those are the two variables that we're going to use for the time complexity here because we need to represent the number of elements in the interior list as well as how many lists we have okay so let's look at this we have one operation i'm going to stop counting these now because we don't need to even consider them in our operations we're going to cross them out anyways it's just one single operation it's constant doesn't matter we can just stop looking at it because it's not going to be based on the size of the input however we have a for loop we say 4 inner list in nested list well nested list we're getting all of the inner lists so how many of those lists do we have we have h of those right h nested lists okay we could write that lowercase h doesn't really matter then what are we doing we're looping through the inner list now the inner list is what well it's going to be w whatever the width is or the number of elements in the inner list so we're doing w here we're doing w here because it's the same thing and we're doing w here so we have h times three w right so inside of here three w operations times h so we get h and then this is multiplied by three w so that gives us three h w and what do we do remove the constants and we get h w okay so we can write this as run out of space here big o of h w and you know we'll just make it uppercase to stick with what we have before so the big o of the height times the width that's the number of operations that we're doing that's our big o uh or time complexity for this algorithm hopefully that makes sense hopefully i'm staying with you guys here you're staying with me actually please leave a comment if it's starting to get super confusing obviously doing this with no one giving me any feedback it's a little bit difficult to know if people are following or not but i think this is a decent explanation we have h in our list so we have h times we're going to do this for loop right here and then inside of the inner list we have w elements right so we're doing this for loop w times this for loop w times as well so we're doing 3w for every h so that's going to be h times 3w for the number of operations we have a constant in there which is 3. we don't care about the constant we remove it and we get w times h great okay next example example five now this is a recursive example uh going to be a bit more difficult here what i would recommend you do is try this with a very small value so try this with number three or try this with a value 2 and see what actually happens when you give it kind of these small values and how many operations end up happening in that case okay so i'm going to go to the screen snip now and let's look at this okay so this is a recursive example is actually a very famous problem it's the fibonacci sequence now i will just tell you that the big-o notation is 2 to the exponent n but we want to walk through why we're getting 2 to the exponent n so we need to understand how this code actually works so we're going to deal with a lot of recursive stuff when we're looking at time complexity analysis and the important thing to look at here with recursive functions is how many recursive function calls are happening in every step so we want to figure out essentially how many times is this function going to run and then we want to multiply that by the number of operations occurring in the function that's how you deal with recursive function calls how many times does the function run multiply that by the number of operations inside of the function now the first thing we're going to look at here is the operations in the function because that's the easiest to figure out so we have these are constant time operations right so we don't need to consider them these all take constant time okay all that so we can kind of cross all those out we don't even care about those now this operation right here this is a recursive function call so we're not going to consider that because that's going to have to do with how many times the function runs again recursive function call and then we have another constant time operation that we don't really care about so if we're looking inside of the the actual function itself we'll just say that the function takes constant time to execute however how many times is the function going to run well that's based on these recursive calls so once we figure that out we'll know the time complexity so let's just do a simple example here with an input of size five so if we have five then what we need to do is we need to call the function at four and at three because we have four here and three here when n is five okay those are the two function calls we need to make from four we're gonna have to make the function call three and two by the way i'm not making these in the order they're going to be done i'm just trying to write out the whole tree from three we're going to have to call two and one okay because our base cases are one and two so whenever we hit one and two we're done so done done done from 3 we're going to have to call 2 and 1. okay so this is what our tree looks like so what you should be noticing here is that we're going to end up getting a time complexity of 2n so the reason why we're getting 2n here is because for each input to the function we're doing two recursive calls so if we start at 5 and we do a call to 4 and we do a call to 3 we've done two calls and then from these numbers we need to do two calls as well now we are going to end up doing less than two n operations however this is the best function we can use to approximate how many operations are going to occur in this function or in this algorithm so we have two recursive calls the calls are going down by any minus one and n minus two so a constant value they're decreasing by not something like divided by 2 or divided by 4 which would be much different we'll look at that in a second we're reducing these by a constant value so the most amount of steps we're going to have to do for every input is 2 and that means we're going to have 2 to the exponent and potential steps now if you want to prove that to yourself keep expanding this tree look at 6 look at 7 look at 8 look at 9 and you're going to see how many operations you have to do and how we expand in this way in an exponential way okay so 2 to the exponent n is the time complexity here this is kind of just a complex do you have to be familiar with again the way i determine this is how many function calls i can have at most now again i will have less function calls than this but this is the most approximate function i can use for the big-o notation so we have big o of 2n all kinds of other videos on the fibonacci sequence that can probably explain that as well in more depth so let's write the comment of big o of n or sorry 2 to the exponent okay now let's go to example six all right example six so this one we have lst and search list actually let me go back i don't know why i keep keep going full screen here let's go and take a snip okay so we're gonna call lst here n and this will be m so two different inputs we have two lists go ahead pause the video determine the time complexity okay so let's get started here so the first thing we need to do is we've got to look at this operation here now a lot of you are going to say that this is a constant time operation it just happens in one right we just count this as one operation now we cannot because what max actually does in python is it loops through the entire list and finds the maximum value so you've got to be careful here whenever you're using internal language features like built-in functions max min stuff like that even you know slicing an array for example slicing a list you need to actually consider what's happening on the lower level and how long that's actually going to take so if i want to find the maximum number in the list the only way for me to do that is to search through every element in the list so if i have a list i have one two three four and i'm looking for element two okay yeah it only takes me two steps to go through this but i still need to say that this is going to take me o n time because if the element 2 was pushed to the very end of the list i would have to look through every element in the list to find it so this is where the worst case comes in right when i'm searching through a list i might find the element immediately or i might find it at the very end so in the worst case i have to assume it's going to take me n time to find the element so i say that finding the maximum element in a list takes me o n time hopefully that is clear so o n time for this first operation so let me just write an n here okay so that takes n to find the max then we're gonna look for a value in the search list so we're gonna say four value in search list and we're gonna check if the maximum value is equal to the value and return true so this here this is going to take us m time now again this might not take us m time if the maximum value is equal to the value in the very first value that we look at we immediately return true and this actually took us constant time it took us one operation to do this however if the value that we're looking for isn't in this list or it's one of the later elements in this list it takes us m time to look through it so in the worst case the element doesn't exist we have to loop through every single element in the search list just to find that it's not there that takes m time now that makes the total time complexity here n plus m so big o of n plus m we do the first operation which is n looking for the maximum element in the first list and then we search through all of the elements in the second list in the worst case giving us big o of n plus m all right let's continue uh example seven okay so this one is a bit more complicated again has to do with recursion uh pause the video take your time and try to guess what the time complexity is okay let's open up our snip here and let's go through this so for this one it is a little bit tricky but we really want to pay attention to this n over 2 here and what's happening in this recursive call so previously when we saw recursive calls or when that one example we saw it we had a time complexity of two of the exponent n now the reason we had that is because we were calling two calls for every single input right so each input five i'm calling i'm calling the function twice and i was only reducing n by a constant amount i was reducing it by two three four one any constant amount that i'm reducing it by is going to cause me to get something like 2n now if i had three recursive calls i would have got 3n if i had four recursive calls for every input i would have got 4n assuming that i was reducing everything by a constant value now here i'm only doing one recursive call and i'm reducing this not by a constant i'm saying n over 2. so i'm actually reducing it by n like n is a part of the reduction factor if that makes sense so when i do something like n over 2 you can see that i'm very quickly going to get smaller numbers so 40 goes to 20 20 goes to 10 10 goes to 5. 5 goes to 2.5 2.5 let's round it goes to 1 right so this is how quickly we reduce from a very large number now this is actually logarithmic okay this gives us the log base 2 of n is the time complex again i'm going to continue to explain this but you need to keep this in mind so we have log base 2 of n so n is constantly being divided by 2. every time it gets divided by 2 that's reducing in a much smaller end right and so that means we only are actually going to do log base 2 of n recursive calls or at least that's what our time complexity is going to be because that's how we're reducing n so again if we start with n equal to say 100 then we're only doing one recursive call and the next recursive call goes to 50. then it goes to 25 right then it's going to go to approximately 12.5 we're rounding this so it would go to 13 okay that's fine goes to 13 we divide 13 by