[MUSIC] Hi, as you know, in competitive programming, your solution has to pass each test in some fixed amount of time, called a time limit. And they are pretty tight, usually just 100 seconds. And usually you're not in it only to do something, but do it fast, and it's going to be challenging. But how to measure efficiency, aside from getting [INAUDIBLE] system? And how to predict in advance, does your solution pass or not? And also how to make solutions faster, we'll find out in this lesson. First, we'll consider an example problem. We're given two strings, s and t, and we need to check if s is contained in t as a substring somewhere. Let's take a look at some possible inputs. In the first s = abac and t just starts with it, so the answer is yes. In the second, s = cac, and in t, there's only one letter c. So s couldn't be a substring and the answer is no. And in the third, s= abab, and t ends with it, so the answer is yes. Now let's develop a solution. We denote as n the length of s, as m the length of t. And notice the most simple thing we could do. We could just take the whole substring of t of length n, compare then character by character with s. And if some characters do not match, then this substring is certainly not s. And if all characters match, then the substring exists, and the answer is yes. And if none of the substring matches, then the answer is no. Let's see how this algorithm works in examples. As we're interested in running time, we'll also count the number of comparisons which our algorithm makes. In the example on the slides, n = 4, and we start with a first substring of t of length 4, which just begins with its first letter. Here the character a is matched, b is matched, the second a is matched. But the first character is b in s, and c and t, so that's a mismatch. We made four comparisons, and solved that the substring is not s. So we move to the next substring of length s or length 4 in t, which starts with the second letter. And here, even the first characters do not match. So we might try a comparison and see that this substring is also not s. Then move to the third one, here the first characters do match, but the second don't. So it's two comparisons as you move to the fourth. Here, also the first characters do not match, and so we make the final comparison. And finally, the last subset of t is s, but we need to check it, for it, we need four comparisons. So in total, we've done 12 comparisons, is it much or less? Don't know, we need to consider other examples. In the second example, strings have the same length as in the first one, four and eight. But here, t just starts with s, so we check the first substring in four comparisons, and see that it's the answer, so we determine yes. So it will be done for comparisons, and that's three times less than our previous example, although the lengths are the same. So we can conclude that the number of operations, and hence the running time, may vary from test to test, even if they have the same size. Imagine that you made a solution and checked it against a sample test, and then some of your own, and it's worked quickly every time. So how can you be sure that you will pass the time limits? In fact, you can't be, because you've checked only some tests, and your solution has to work fast on every test. In other words, universalizable test, where the number of operations is maximized. [INAUDIBLE] try to think about what is the worst possible case for different solutions, and include all of them in a test set. Let's imagine that we are creating tests for the substring problem. And let's think about what is the worst possible case for our previous solution. It makes sense for the answer to be no, so we need to check every substring. And it will be perfect if we need to compare each character in each substring. And the mismatch will be only at the last character of s. In fact, there is an example just like this, s contains character b but t doesn't. So the answer is no, and thus, every character of t at every character in s, except the last is a. We need to check every pair of characters while we're checking every substring. In the first substring, we compare the as and they match, only the b is a mismatch. And the same the second, and in the third, and then the fourth, and then the last. So we make 20 comparisons in total, and that's way more than our previous examples. So to conclude, we've seen that the number of operations could vary greatly even on a test of the same size. So we can just take a big enough test of the worst. Finding the worst possible test case could be very involved. And the measure of the number of operations, we need to have an implemented solution. It would be good if we could estimate running time without needing to implement the solution beforehand. So we want to estimate performance of our solution on any inputs without explicitly constructing anything. And that's what we'll do in the next video.