In this video, we'll learn a powerful technique for estimating the number of unit operations in an algorithm. In fact, it depends on inputs and we'll measure the dependents. As indent, we want to estimate the running time, we want to count unit operations. The operations which take some fixed small amount of time. There are several important examples of them. They include, operations with numbers like arithmetic operations and comparisons, logical operations, which could be found in statements and or, working with an individual value in an array, defining a new variable. In fact, these operations do not take exactly equal time. Some of them are faster, some are slower, but only slightly. Like the slowest of them is two or three times slower than the fastest. However, there are operations which may look just as simple but in fact, be much slower. And most importantly, it's operations with some basic structures like strings or lists. And the examples are, comparing two strings, building a new one from many elements, or concatenating two strings. They are generally slower because strings and lists consists of a number of small elements. And when we do such operations, we need to do it for each element of the big string or list. And so, it's in fact not one operation, but many unit operations like comparing characters when we're comparing strings. Now, remember the substring problem and our simple solution to it. That Python-like code for it could look like this, n is length of s, m is length of t. First, we iterate over difference substring of t of length for n and adjust their positions from zero to m minus n. Then for each substring, we need to check if it's equal to s. We just compare characters one by one. And if some pair doesn't match, we break and move to the next substring. And if all are matched, then the substring is s and you could say that the answer is yes. If in the other hand, none of those strings has matched, you could say that the answer is no. Now, as we have the solution we could count the number of unit operations. But let's look at the following line. It's just a simple if statement, but in fact, here are five unit operations. So the issue is, even for the simple solution, it's tedious now to count all operations exactly. On the line from the previous slide, there are five operations which is not all but most importantly it doesn't depend on anything. No matter what the inputs will be or which iteration is it right now, it will always be five operations. And in fact, the key idea is instead of counting all the operations explicitly, let's just say that there are a constant number of them. So how can we bound the number of operations in a previous solution? The outer loop does no more than m iterations. The inner loop always does n iterations. And the code inside it that's constant amount of operations. In fact we don't need to count, it disappears exactly. We could just look at the code and see that's the sample is constant. In total, there is no more than m times m times constant operation in our solution. In fact, there are also some operations which happen outside the if statement but their result is also constant and is going to multiply it only by m. So in fact it's counted in our bound. And the good about the bound is, we don't need to consider any explicit examples to get it. We just look at the code. And thus it's independent of any particular test, this bound works on all tests. So let's formalize what we have done for the general case. Variegation upper bounds on the number of unit operations up to a constant multiplier. The idea is that constants arising from different solutions are not very different. They pretty much the same by magnitude. But what really impacts the entire the most is the dependence on their input size. Formally, let n be some parameter of the input, like one of the input variables or the size of input string. And let m be some function of n, for example n squared. Now to the most important definition, we say that an algorithm has asymptotic time complexity of Big-O of f of n, if on any test it makes not more than C times f of n operations. Where n is the parameter of that particular test. And see it's the same for all tests just on constants. For simplicity, there was only n in the definition above. But you could define the same definition of s in several parameters. And for example, in our substring problem, I guess complexity of Big-O of m times n. Now how to get these bounds for any solution. Let's state some properties of the Big-O notation. First there are always upper bounds. We're just saying that our solution makesno more than constant times something operations. But that doesn't mean the direction of operations is equal to it, it could be less. For example if we know as our solution is Big-O of n squared, it could also big-O of n. If it actually does, no more than n time constant operations. And if our solution solution is Big-O of n, it's always Big-O of n squared, because n is less than n squared. Then we see the optimal bounds, which is just upper bounds but does actual number of operations which all could be false on the worst case test. But they could be as involved in different algorithms and there is no general method of obtaining them. But you could obtain some parts straightfoward. I started with a substance problem. And in fact, they could also sometimes be optimal. We will do that somewhat inductively. First we'll bound the number of operations of a single statement then of some piece of code inside the loop and so on. For a single statement it's actually simple. If it just contains some constant number of operations like the flying from before, then it's constant time or Big-O of one. If it uses some built-in structures of functions, it depends on them. So you need to know their time context in advance. And they can be easily found in documentation. For structures it usually depends on their size. For example comparing strings is linear. Big-O of n if n is the size of a string. And any operation that iterates through several elements most likely takes at least size operations to complete. It could also be a call to your own function. But then you just need to separately bound the time complexity of that function. Now let's see what happens with simple loops. Say you did i to n, and the code inside is Big-O of f of n on every iteration. So in total the complexity will be Big-O of n times f of n plus n. Because the inner part is repeated n times and so it's not greater than n times f of n. And also little by itself takes about constant times on operations, because it needs to implement the loop variable and check the loop condition. Of course actually this code could be faster as the inner parts could break out of loop sometimes or on most iterations, there can be less operations. But our bound is still correct. And to improve it, you would need to analyze the particular codes. Now lets consider recursive functions. Remember the simple recursive of backtracking from the lesson but for solutions, and particularly the problem of enumerating all strings of length n consisting only of characters a and b. We've got recursive function that looks like this. And how to estimate the number of operations in here. In fact you could just remember that this code does the same as n nested for loops. Each iteration over two letters, a and b. The total number of operations is two to the power of n. And the inner part you just print x, as x is a list of n letters printing it is linear time Big-O of n and so in total we get Big-O of n times two to the power of n. In this video we've learnt what are the Big-O bounds and how to obtain them. And the next one will see how to really estimate the linear time of an algorithm using the Big-O bounds.
