Efficiency and Big-Oh 3: Time Complexities and Theorems

this is a list of growth functions that you will commonly see when analyzing computer programs listed in order from smallest to largest now some of these are more common than others the first of these isn't even really a function it's just the value one what this means in the context of a computer program is that the runtime of the program does not depend on the input size now this doesn't mean that the program is slow it simply means that the execution time does not grow with the side of the input this is also known as constant time next we have log of log of n and then log in and then log squared of n now all of these logarithms are assumed to be base two so this here log in is assumed to be log base two of n however I'll demonstrate at the end of this video why the base isn't really irrelevant when discussing Big O you may also find this notation here curious this log squared of n is simply equivalent to the quantity log of N squared but we can't write this without the parentheses because then the end would be squared and so we move the squared next to the log rather than having to write this parenthesize quantity all the time of these three categories this one here where it's a plain log is certainly the most common and this is simply referred to as logarithmic next we have in by itself this is what you typically get with a standard loop that executes some in number of times and so this is linear then we have n times log of n and then in squared this is quadratic and in race of the three is cubic and I won't list any more out but obviously if you increase the exponent you'll get larger and larger runtimes so into the four is greater than n to the three into the five would be greater than that and so on but all of them no matter how big that exponent is if it's a constant value it's going to be less than two to the N and this is an exponential function now I won't list all of these out but 3 to the N is larger than 2 to the N for the N is larger than 3 to the N and so on so as we increase the base we get larger and larger functions that take long to execute this last one is factorial and in case you forget what this notation means it just represents in times n minus 1 times n minus 2 going all the way down eventually to 3 times 2 times 1 and so this is factorial and of the functions I've listed this one is definitely the worst so hopefully in your code you'll avoid these really expensive functions but sometimes you can't so given this order what it means is that if we write out a function that contains several of these sort of functions as sub functions that all we can do is focus on whichever one is largest and also we can ignore coefficients so if I have a function like this this function contains in cube and squared log of n and a constant term but this is Big O of n cubed because N squared is less than n cubed the log n is less than both in the constant is less than all of them and we get rid of the coefficients this is the coefficient for that term this is the coefficient for that term that's the coefficient so those are irrelevant in the simple big of functions that we tend to use and here's one more example so in this function to be in is the portion that grows the fastest and therefore the Big O of this is to the N now at this point a bit of caution is needed in terms of how we speak of these functions I said here that this function is o of 2 to the N and this function is o of 3 the N those statements are true but if you think back to the strict definition of Big O all it is saying is that if you multiply this function by some constant it will be larger than this function when the value of n is sufficiently large now technically what that means is that this first function although it is true that it is Big O of n cubed it is also o of 2 to the N and it is also o in factorial because these are also upper bounds on that function so anything that is larger also qualifies as an upper bound however it's generally understood that when we talk about Big O what we care about is the tightest bound the smallest function so although it is true that this function is o of 2 to the N that is a worthless piece of information what matters is that it is o of n cube because that is the smallest function at least among these functions we will commonly see that actually tells us something worthwhile about the runtime of this function here so whenever we talk about Big O we always care about the tightest possible down that the smallest bound the strict definition gives us leeway to pick some arbitrary large function but that's not useful so we want to pick the smallest function for which our claim about Big O is still true so the fact that when you add a bunch of these functions together all that matters is the one that grows the fastest can actually be formalized with a theorem so this theorem says that if f sub 1 of n is o of G sub 1 of N and F sub 2 of n is o of G sub 2 of n then if you have a function that combines those two sub functions F 1 of n plus F 2 of n then this is going to be big-oh of whichever of those two G functions is largest the maximum of G sub 1 of N and G sub 2 of n so an example of this is if we have 5 n cubed plus 2 log in well in this example this 5 times n cubed we are f sub 1 of n and this 2 times log n would be our F sub 2 of n now we know that 5 times n cubed is o of n cubed so we're going to say this is o of the max of n cubed and 2 times log of n is o log in so that is our G sub 2 so this here is G wanted N and the log n is G 2 of n and so the larger of those two is the n cubed so it's actually o of n cubed now this example I just did actually relies on another theorem which is fairly obvious but it's worth formally stating if f of n is o G of n then that means that some constant a times f of n is also o of G of n basically indicating that constant multiples are irrelevant because the definition of Big O allows for us to define some constant already anyway so this would just sort of be calmed over into the definition so this is fairly straightforward to prove I won't elaborate on more but this claim here is the reason that five times n cubed is o of n cubed here's another useful fact if F sub one is o of G sub one and F sub two is o of D sub 2 then that means that the product so if you multiply F sub 1 of n times G's F sub 2 of n then the Big O of that is the product of the two G functions G sub 1 of N and G sub 2 of them so an example of this would be if I had something like 5n squared plus 7 quantity times 7 log in so I'm multiplying these two together but the Big O of this would be N squared log in because if this is our F 1 of n then n squared would be the G one of them because five squared plus seven is o of N squared and if seven times login was our F 2 of n then log in by itself would be our B sub 2 of n by this previous theorem I mentioned here where the constant K in this example is 7 we can apply these concepts to actual code as well so here we have a rather large java method and we want to know what the overall runtime of this code is so first I want you to note that we have this for loop here in this for loop here so whatever the runtime of this method is it's going to be the time for this portion added to the time for this portion so we're basically just adding those together the other thing I'm going to point out is that we have a nested loop we have this loop inside of this loop so if we can figure out what this loop is in isolation and then we can figure out how many times this loop repeats and that is essentially multiplication so first we want to look at how many times this loop runs now before we focused on counting individual statements but I think it's clear at this point that what really matters is simply how many iterations we have how many loop repetitions actually occur and we can even be a bit vague as to the exact number because if we add one or minus one it's not going to affect the terms we care about because we want to know the growth behavior so getting it down to the precise number of statements is not as important when all we care about is a Big O so this loop starts for I equals 0 eyes less than in but extra complication I plus equal to two that's a little bit different but not in a way that really matters if we were simply doing I plus plus then it would be obvious that the loop runs in times but if we're doing I plus equal to well that means we'll luke fewer times will reach our termination point faster but all we're doing is splitting the number of iterations in half so this loop will run one half of n times roughly so I'm going to put one half in as the count for this and then there's a statement there which we could ignore but I'll go ahead and include it just for now and then we have this loop and this is actually something a little bit different than what you've seen before because we loop as long as K is greater than one that's not surprising but the variable update is K divided by two so K is set to itself divided by two and so what is the runtime of this loop well it turns out that this is actually a very common way of getting logarithmic behavior because if we start off at N and we keep dividing by two until we reach one or zero or some other small value we have to increase in by a lot to get one extra loop out of this so the number of iterations of this loop here is roughly log of n specifically log base two of n because we're dividing by two then we move on to this next loop this loop goes from I equal to 1 I less than equal to n i x equal to 3 and so this is actually another common way of getting a logarithmic loop now technically because we are multiplying by 3 this is log base 3 of n but I'll demonstrate in a moment why that distinction doesn't matter it was mentioned earlier that we assume all of our logarithms are base 2 and there's a theorem I'll show you that says that log base 3 of n is o log base 2 of N and so if we take all of this is given what we essentially have is a function that is something along the lines of one half in times quantity 1 from this plus log 2 of N and if we wanted to account for the fact that there is the test and then those two statements we could multiply this by 3 once again it's all going to disappear in the end anyway so that's a quantity and so this takes care of the entirety of this loop with an inner loop that's being added to this result here the log base 3 of them but we can figure out the Big O of that by just looking at the individual components so we know that one-half n is o of n we know that this complex little function here is o log base 2 of n or simply log in and I already mentioned here that log base 3 of n is oh a blog 2 of N or simply log it in given those facts we can apply both the rule about adding functions and the rule about multiplying functions to see that when we multiply these two together that bit is o in log in and we're adding the log in but in log n is more than log in so it's irrelevant it just reduces down to this I guess that the step that I'm skipping is that this is the max of in login and log in but that means that the final result is simply Oh in login so all of this code here has a runtime of in login and it's primarily because of this because this portion will take longer to run than this portion so this portion controls the growth behavior of the function whereas this is subsumed by the longer running portion here so why is log base 3 of n o of log base 2 of n well this actually relies on an even more general fact that log base anything of n is o of log base anything else of n so keep in mind that a and B here are both constant numbers but what this means is that a could be 3 and B could be 2 it also means that a could be 2 and B could be 3 so log 2 of n is o of log 3 of n but it's also true in the opposite direction which is kind of weird but we're gonna prove it it actually hinges on this change of base formula for logs which you could be forgiven for forgetting it looks like this log base a of n is equal to log base B of n divided by log base B of A and remember very important in all of this that a and B are constants now what that means is that this portion log base B of A is the log with a constant base of a constant value so that is also a constant and the fact that this is a constant makes proving this fact here fairly straightforward using the definition of the ago so we'll start with the function on the left and we want to show that this is less than that quantity multiplied by some constant well according to this change of base formula it's equal to this but when we're dividing by a value we could simply rearrange things so that we have one over that value multiplied by the thing on top numerator so this will be true for any constants a and B and so what that means is that this is equal to C times log B of n for C equal to one over log base B of A and we're defining a constant but this is allowed because log base B of A is constant the only thing we're missing is our value K and technically we prove equality but if it's equal then it's also less than or equal as well and this is going to be true for anywhere that the logarithm is defined although logarithms are only defined for values greater than or equal to one so our K equals one and so that's why all logs are equivalent for the purposes of Big O

Channel: Jacob Schrum

Views: 221

Rating: 5 out of 5

Keywords: big-Oh, theorem, proof, time complexity, order, log, logarithm, linear, constant, quadratic, cubic, exponential, factorial, change of base, formula, prove

Id: ydsZi1ZFmsk

Length: 21min 20sec (1280 seconds)

Published: Tue Jul 14 2020