Video 4-8: Better FPT Vertex Cover & Linear recurrences

0:02 We'll come back to the vertex cover problem in this section and um we'll see both a more interesting algorithmic trick in this in this case uh but also one that poses some challenge for the analysis.

0:24 Uh recall the very simple um FPT algorithm for vertx cover. It was virtually the first example we've seen after the one for for SAT. Um it's the first one where we get something that's not completely obvious. You can branch on on the two end points that gives you a search space of two to the K for vertex cover. Uh after that you either have a vertex cover of size at most K or you know there is none of that size. and vertx cover is a bit um if satisfiability is the standard problem of complexity theory in the classical sense uh for for fixed parameter tractability I guess vertex cover is is somehow the the default problem uh that people try out uh tools first so certainly we can do better than that there's a bunch of work on on vertex cover but here um I'll I'll focus on a on a relatively simple idea Okay.

1:20 Uh how to improve the 2 to the k. Um one option is to have uh larger base cases. So cases where um we can find or argue reason about the uh optimal vertex cover sizes without doing a further recursive step. We don't need the exhaustive search. And so consider the case that we have a graph where all the degrees are at most two. These are very restricted types of graphs. What can they look like? Well, it could be isolated vertices, very boring for vertex cover. It could be um a path of of vertices.

2:14 um be a path that loops back on itself otherwise known as a cycle and it can be a disjoint union of these but that is it. You cannot build any trees or anything else more complicated like a even a branching of this type right that's already degree three. So that is not allowed. So really it's it's long chains and cycles. That's all. Very simple graphs. So what would a an optimal vertex cover for this graph look like? Uh let me add one more one more vertex to our graph to our path here.

2:54 Um, in the path case, you really just want to start not at the end points. But if you take every other vertex along the path, that's an optimal vertex cover. You have to pick for each of these edges that are not the outermost ones, you have to pick one of the two end points. And the only thing you could potentially do uh wrong is start with the outermost end points. then you would have size three here whereas two is possible. That's for oddlength paths.

3:26 And cycles are virtually the same except they don't have a start. So you basically start wherever and pick every other vertex. And in the case of odd cycles uh you'll have to have two adjacent vertices but that's inevitable otherwise you don't cover all the edges. So what I'm saying here is if you have these special cases of graphs where all the degrees are at most two uh finding the optimal vertex cover is a linear time algorithm. You just uh find the connected components of the graph. That's a depress search. And then for each component you learn already uh what it looks like. Is it a cycle? Is it a a path? And basically taking every other vertex avoiding the end point is all you need to do. Okay. So very simple and uh nothing nothing deep there. Uh but somewhat surprisingly maybe this helps us. Uh the point is that if we uh if we solve this special case we can increase our um assumptions for the remainder of of the algorithm.

4:49 uh if that's not applicable then the degrees are uh first of all not in zero one or anything uh larger than k. This was the reduction we had already in the kernel uh section. Degree zero and degree one vertices. So these guys are boring. These guys are boring. We can always get rid of them. And highderee vertices. You also know knew that you know you can always pick that vertex because it wouldn't be feasible to take the neighborhood instead.

5:29 Um plus we know that there is now at least one highderee vertex where high means at least three. That's the new thing. This base case gives us there is a vertex of degree at least three.

5:54 Okay. So here's a simple algorithm just based on that idea. is almost the same algorithm as before just added a part here. So it's uh the sim same same same kind of uh depth bounded search idea. Uh we have a graph and we have um a parameter k how many edges can we still pick. If the graph has become empty then we can just return the empty set. That's a vertex cover and it's a minimal one. If k is zero but we are not in the empty case then there's nothing we can do. we cannot cover the remaining edges otherwise we have to maybe work some some harder so we check if we're in this easy case um and if so we know how to solve it so here I just spelled out in in English sentences uh how to do it and it's kind of a an undergraduate level um algorithms exercise to implement that with depth for search in linear time so we're not going to worry about the details details. The interesting bit starts after that. If this is also not the case, if we don't return here, then there must be some vertex um might as well take pick the one of largest degree. Uh so V is that vertex and W are the neighbors. Now to cover V's edges, we either have to pick V uh take V into the vertex cover or all the neighbors otherwise we don't get these edges covered. And that's what the algorithm uses. There's these two options to recurse on. Um either I'm removing V and all its incident edges or I'm removing all the neighbors with their incident edges and uh I guess V alongside of it.

7:52 um and I'm trying to solve recursively the problem where now the graph has some vertices removed and also the parameter is reduced by how much well by how many vertices I add to the vertex cover or the potential vertex cover so in the case I pick V I only get a parameter that's one smaller same as before but for the second recursive call where I take the whole neighborhood I reduce the parameter by at least three and maybe more. And that's the magic of the whole uh base case. It means at least one of the two recursive calls makes more progress by reducing the parameter by more than one. Okay.

8:55 Good. Now the question becomes what's the running time of this method. A few things um we can say which are easy. Uh for the worst case we can assume we're always going to be in the case where we have to recurse further. Say the original graph doesn't have many lowderee vertices. Um so we're never in this case or at least we analyze the the the cost for for having that case. We always need both recursive calls. We're not like uh in the lucky case where one call returns early and already found a solution. Um and what we'll ignore for the analysis which is bit wasteful um but we'll uh we'll make the analysis easier is that the graph is growing is shrinking a bit. We're removing some vertices. But remember uh so the setup the setup is that the graph is really big and the parameter is relatively small. So the fact that the graph gets slightly smaller doesn't help us all that much. It means that this some of the base cases get slightly cheaper over time uh but it's not a big difference. So that's just to make the analysis a bit easier and we're upper bounding the cost of the algorithm.

10:33 So then uh what we get is um a recursion in the parameter k the graph we treat as uh staying the same size or we upperbound the cost by the original size. Uh but the parameter is what changes and that's the interesting bit where we make progress. So if the parameter is zero, we pay constant time for uh the base case. That's uh just returning immediately. And for the general case, we assume we have to do uh some linear time for example for for shrinking the graph or finding this largest uh degree vertex. So this will this will be linear in the original input size. And we have the two recursive calls where we reduce the parameter by one and by three respectively. Okay, so that's set up clear. So if we can solve this recurrence, we can get the analog of what we've uh analyzed before where we said the the search search space size is 2 to the k. Previously we had or the simple FPT vertex cover. This would have looked similar.

11:58 We have a base case and then we have two recursive calls of uh the same size before and I guess the pre-processing is a bit easier. So maybe we don't need this extra uh term. But to be Okay, let's let's call this n and this m in the usual notation for graph algorithms. Okay, now this recursion here was trivial to solve.

13:01 Um okay one one more step we can do uh to get rid of this this extra term is uh we're basically um building a tree. So this is the recursion tree of the two recursive calls and I guess the right ones is going on for longer because the parameter doesn't shrink so much so the tree is a bit lopsided. Now uh here uh this is is a different recurrence which is easier which is counting the the base cases. So just the number of [Music] um the number of of vertices that don't recurse further. Now because this is a binary tree the number of uh recursive of of internal nodes so the number of uh recursive calls that do further um so I guess these are non-leaf recursive calls or non-base is their number is is bounded by the number of uh leaves because it's a binary tree. So um we would normally pay this term and this doesn't depend on K because of our assumption here. So I I would pay uh this order m cost in each of those red vertices. That's the true cost I have. Okay. And here and here. And I can upper bound it by instead paying it at the green leaves. So tk is effectively [Music] um this uh theta n + m times the number of non-base cases, but that's essentially the same as taking the green ones. I just So we're counting the we're taking the green recurrence instead of the red recurrence. If we at the end multiply by so I guess I should have uh added this part that's the BK then right? So if we solve BK we can just multiply by N * M or N plus M sorry and then we get the overall cost for the original algorithm or an upper bound for the original uh algorithm.

16:05 That's the idea here. Uh and the reason is is just that we get rid of this extra term with a different parameter. Uh that makes life a bit harder and the base cases are easier to count. Um yeah, I'm I'm adding here the base case for parameter size two.

16:30 Um, I guess if you're if you're asking here's a graph, can you find a vertex cover with two vertices? Uh, you might try all pairs of vertices and that's still um roughly within that time bound. I guess it's n squared, but uh maybe you can do slightly smarter by just going over the edges. I guess two vertices this like a if a graph can be a vertex covered by two vertices it's going to be a a very boring graph it can have a single edge so that base case I'm technically cheating a little bit that base case is not part of the uh pseudo code here u but we could we could add base cases for k equals 1 and k equals 2 and they wouldn't do anything interesting thing on the other hand uh what we really do here is uh find a vertex and then do one step of recursion and we're done anyways.

17:46 question. So yeah, the question was uh can you can you cache the results of the recursive calls um as in dynamic programming? Um and the answer here is no, at least in general because the input for the recursive calls is different each time. uh it depends on the path of uh you start at some point with the same graph uh as the input but then you take away a certain subset of vertices and there's many different subsets of vertices you could remove there's too many subsets so in you could you could formulate it as a dynamic programming instance but the number of sub problems would be exponential number of subsets and so it's not going to help. It's is essentially doing the same as this. I wouldn't really uh reuse anything. Yeah, it's a good point. There's there's superficially these algorithms always look similar but then uh is a big difference if you have um a polomial number of subpros or an exponential number. The code doesn't make this so explicit, but subsets explodes. Um, I don't know what's a number of pairs of integers doesn't explode. That's maybe a typical dynamic programming sub problem. A range of some some array. Yeah. So, take take the uh recursion with a slight bit of slack.

19:23 It's not going to give the exact time in the sense we want to analyze algorithms in undergrad introduction courses. This is going to give you the right exponential growth. Um and it it gives you roughly the right polomial factors. Um maybe there's a for this case a slightly higher cost than for the other base cases. But this is not going to affect uh the overall growth. It's even vanishing in the big O. It's just a constant factor difference. But still like uh this kind of recurrence. How do we solve that? Uh this looks much more innocent. It has similarity with the Fibonacci recursion. Uh except that here it's a minus3 not a minus2. Uh but how how should we know how quickly this grows? And um this is a a prototypical case. Many uh fixed parameter tractable algorithms of this sort of a depth bounded search they end up having the same kind of analysis where there's different recursive calls and you reduce the parameter by different amounts in each of the cases. So you often end up with questions like this.

20:41 What's the exponential growth of this? Is this better than 2 to the k? Uh so let's find out. And what I want to show is on on this simple example and I'm trying to do it live um so that you see the method without any kind of um uh shortcuts. Uh so let's copy the recursion first. Uh we have B2 is B1 is B 0 is one and we have B K is K - 3 + B K -1 and we'd like to solve this or at least get a a feeling for the exponential growth. It turns out we can exactly solve this always whenever the recurrence looks like this. uh and I want to teach you the the method more so than the concrete example, but I decided to do it on the example instead of trying to give the general construction uh because I think it illustrates the key points and then it's not a um a discrete math class. So maybe some of the generalizations that you would need for the general case we don't care about. Okay.

22:03 Um the first uh the first step is to do something weird. We're going to define some function which is a series an infinite form. And uh you'll have to bear with me a bit for why. For now, I'm just claiming this is going to help. And this is called the uh ordinary generating function of that series of that sequence of numbers.

23:00 Okay. Um first objection is this is an infinite sum. It might not converge. It might not be uh any reasonable value. Uh the short answer is it doesn't matter for the technique. It kind of works either way. Um the second answer is it will converge if set is small enough. the absolute value of zed is um say 0.01 then this exponential growth here means we're shrinking these these uh coefficients by so much that the sum still converges. It's a bit like um the geometric series converges if you take um a good starting case. What's that series? Does anyone want to shout a shout out? And you can keep thinking while I'm trying to find it on the cheat sheet. I think these the series are further back. Might misremember I think it's on the No, this this is basic is on the front. Uh oh, but there is some mention of generating functions. So, while we're there, I might as well show this part. Uh one more. So, uh ordinary power series is what it's called here. And uh so you see it's a thing.

24:44 Um and there it is. So uh the same formula also appears under different names on the first page but this is this is the one uh it's looking here it has an x instead of a zed but that's the only difference and it can be written in closed form as um okay maybe uh let's also take the screenshot just as a proof.

25:28 Right. So that that's just here in tiny because not going to use it that much for now. So 1 / 1 minus zed uh that's an kind of an algebraic identity. But you can also make out that this as a function of zed. This is going to run into problems if if set is equal to one, right? That's one obvious thing. Then you're dividing by zero. Uh it seems to work fine if set is bigger than one. Uh even though this thing on the left doesn't seem to make sense. Um so uh uh the cheat sheet doesn't doesn't give more detail on this. uh some of these identities here should only be used if set is small enough. Um but it turns out as an algebraic identity it works either way.

26:19 Um now this is also the generating function or the ordinary generating function of a special sequence namely the all one sequence right because if you set BK to one you get exactly this and then you can write it in closed form which is my uh proof by example that these these infinitive the these infinite sums they can sometimes converge and they often have even a nice closed form. So now um that's maybe a first hint that potentially you can go from sequences to generating functions do some math on the generating functions for example use formulas for series like this and then we would need a way back. Okay. And uh we can define a notation for that. So I'm sticking with K. We define this thing to mean BK if uh capital B ofset is the ordinary generating function of the sequence BK. That's just a definition. In general, that's not all that useful. uh it's a good notation but it's only useful if we can also get back from the closed form or from some representation of this generating function to the coefficients the se the sequence that we started with and let me switch back again to the cheat sheet because it's right here in general there is a way to get back and that's called Taylor series expansion uh often people learn about is um in engineering math to approximate functions. But here we're going to use it in a different way.

28:34 So often times um tailaylor series are used in in the sense of giving some function which may be complicated. Can you approximate it locally by a polomial and that's if you uh if you stop after some point it's in general an infinite sum uh but you can stop at any point and then you get a polomial that approximates that optimally approximates that function close to a certain point. So I guess uh here um the point of development is is at a equals z. So is is that x= a sorry and that's what this function gives. It tells you uh in closed form what the best polomial looks like. Namely um it's written in this form that you have x minus a to a power. So you would have to expand that for the normal form of a polomial and then the factor in front is the uh a certain derivative of the function divided by i factorial. So in general we can get the coefficient back by just using this this function here.

30:09 Um we use a equals zero in our case. So then all these uh just cancel and it just becomes x x^2 x to the i. Right? So um if we take b to the z and develop it around zero I'm just writing this down once so that it becomes a bit more obvious for you. It's B of 0 plus Z times B prime the the first derivative then Z set squared then the second derivative of of B uh sorry at [Music] zero here I'm inserting the development point that should be zero all the way divided two. Let's do one more. Um the third is third derivative at zero and you divide by 3 factorial or six. Um so in general if you want the function to be exactly represented then you should continue uh at infinitum with this but you can also stop at any point and then you get this polomial approximation. So this is how normally people learn about Taylor series expansions especially in some engineering math class. If you've ever wondered how pocket calculators compute the sign function or cosine and all these things they can't actually compute sign. They compute an approximation using tailaylor series expansions and then they can evaluate the resulting polomial efficiently. So it's very widely spread and you use it all the time. But here we're we're going to use it in a totally different way. We're just using it symbolically. I can get back this kith coefficient if I just have the function by uh taking the coefficient. So here you see this is exactly the way um we would represent the ordinary generating function.

32:24 It's an infinite sum and it has the power of of set to the k and then it has a coefficient in front. Let me write the coefficient first. And the coefficient is exactly this uh k derivative divided by k factorial. So if we want to plug the coefficient at set to the k, we just have to pick this part, right?

33:04 So uh so far so good. Now this is actually utterly useless. And the reason why it's useless is computing the kith derivative in the general sense like what I'm giving k as an as a variable and I want I'd like a closed form for what the kth derivative of a function is and the function is something awkward in general. This is this is hard. It's not clear what the kth derivative of something is and write that down easily. Now, in in simple cases like for this function, you could actually work it out what the k derivative has to look like because there's a pattern of the derivatives you can guess. In general, this is useless, but you can use it to compute the first few terms. We're going to use it. So, here I'm just making the point it is possible to get back from the generating function to the sequence coefficients. And there's a there's a a concrete formula how to do it. It's just not very convenient to use that most of the time. Instead, what we'll do is start with a sequence, go to generating functions, move around the closed form terms, and rearrange them, and then use equalities like this backwards. And that's going to be all that we need for solving these. And you can use this all as a kind of just a um a purely algebraic method. um that doesn't need to involve any derivatives or uh any anything about functions in terms of set. It can be just a a way to um make use of existing formulas. Okay, this is is getting a bit uh abstract. So let's continue with a concrete example.

35:11 So what we'll do is we'll start with our actual sequence and try to get something better than this uh general representation for the generating function. And I'm starting here so that we still have the recurrence here uh with us.

35:29 So the the general sum is uh k from let me just write k greater equal uh zero then bk time set to the k. All we know about the sequence is the first few values and a recursive representation. So we have to use that. There's pretty much nothing else we can do. So uh I can insert the base cases right this is going to be 1 * set to the 0 for b 0 + 1 * set to ^ 1 for b1 + 1 * set to the c ^ 2 set 2 for b2 uh and then plus the remaining terms which maybe has a why does this keep happening I'll first start uh just saying symbolically this is bk time set to the k but now only summing from three onwards is a worth stressing here now this recursion I I guess I I didn't copy it here this is valid from k greater equals 3 is It doesn't make sense to talk about k bk k minus 3 if that's not uh at least zero. But here I have k greater equal 3.

37:05 So I can now insert my recursive definition. Okay. So this thing can expand to b k min - 3 + b k minus one. And that's what we're going to do next. So I'm continuing this equation for B of Z and um we have these terms. So it's 1 + Z + Z set 2 plus now these can immediately split. So they're inserted here but then I can take the sum apart. So there's one sum k greater equal 3 b k minus 3 set to the k and the second sum k greater= 3 bkus1 set to the k. And now we're going to try to simplify this to get something back in terms of K because this almost looks like the original B of set except that it doesn't perfectly match. There's a mismatch between the index here and the power and there's a mismatch in where the sums start, but it's actually close. So, first of all, I can pull out three sets um in front of the with at least matches in the uh exponent and and index shift. And I can do the same here with pulling out one set. So that's good. We're closer to this. The only thing that's now not quite right is is this uh k minus three business.

39:10 But if you uh stare at this first sum a bit, we're starting at three, but then we're always subtracting three. I might as well start at zero. This the same thing. I'm just doing an uh change of variables. Replace k by uh k minus 3.

39:36 So if I start at zero instead of at three, then I'm starting at zero in each of these cases. BK and set to the K. And here I can do the same, but um it doesn't quite work. I still have um the sum starting at two.

40:05 Now I'm uh I'm moving in slow motion here but uh I think it's worth doing for illustrating what happens. This thing now is exactly the same as B offset. Uh and this thing is is almost the right thing. It's just starting a bit late, but we can pretend it's be offset and subtract the first two terms again. So if you want, I can add zero by um saying I'm adding B2 set squared. H sorry that one's there. Um B1 set to the one B 0 set to the zero. and then subtracting the same thing together. These two together are now again um a b of set. So what I get is B of set on the left side from uh up here equals these guys uh minus these and this is actually one right this is one. So uh some things cancel and then um I lost lost ah okay they don't cancel uh because I lost track of the factor set here. So that has to go in front of uh the entire thing. I guess I messed up the spacing now.

42:05 So this factor I uh I lost and it should be here. So there's a factor said around all of this uh which means these won't cancel but it's still true that this together with these is my B of set. Okay. But first this term. So set cubed B of Z plus Z times B of Z. And then what's left of these uh there's the minus minus Z squared and minus Z. So I guess uh some things do cancel out but it's different things that I previously had. Okay. So we have uh one that's a plus. Where did the minus come from? Oops. Okay. Now, that's a lovely equation that I can solve for B of Z.

43:30 Um, and we can uh we can try to bring all the B of set terms to one one side. So, it's B of Z* 1 then minus Z set cubed and minus Z.

43:45 And what's left on the other side is a one. Well, I know what B of Zet then is, right? It's one over 1 - Z cub minus Z. Oh, so look the generating function has a nice closed form. And um this is something we didn't have before. Now the question is how to make progress from there. And um this is something uh again that is somewhere on here. Um we'd like eventually to use one of those equalities and there's a bunch more um backwards. So we're trying to find any of these terms in what we've derived for the generating function and use it backwards to get back to the sequence. Now that in general can be tricky but the kind of functions that we have make it possible in the general case. All we need is uh partial fractions. Now there's a formula somewhere on this partial fractions here. So this describes the the general recipe um on our example. Can probably do it more easily or we're going to cheat. So you're going to remember 1 / 1 - set cub minus set and uh we uh take a little help from our friend called algebra and I know there's a an a function called a part that does this but maybe we can also do. Okay, let's first type was 1 over 1 minus set cubed minus set. Um, okay. Yeah, that's right. Okay, let's see if it can say partial fractions immediately. Partial fractions of that.

46:00 So people know Wolf from Alpha is a lovely tool where you can take um natural language input and it translates it into Wolfrun language or their mathematical language. So you should always double check if the input that they understood from your query is what you had in mind. Uh but apart from that the rest is provably correct algorithms. And so uh here they give some representation. I guess we want to see the approximate form. That doesn't look too useful, but it's it's what we need. It's just not super nice.

46:58 it. Too bad. So we'll have to do it manually and this might might not be super nice. Okay, that's the danger with picking the real examples.

47:10 Uh the thing about partial fractions is we can if we have a a rational function so polomial on top polomial on the bottom numerator and denominator we can always find a representation for this where we have the roots of the polomial and uh I guess this is something where I'm going to ask for computer algebra help again but say the roots are set um zero set one set two then I can find a representation where one and another constant divided by Z minus Z set 2. And so we need the roots of this polomial to do that. And I get the feeling that this is not going to be a nice a nice number because this is a polomial of power three degree three. Come on somehow stuck. So we take our polomial and we can ask for the roots. Uh that's something it can easily do. Yeah. So it has uh an exact representation but they're not very nice. Uh so we'll just take the the approximate form and that's going to make um the remainder a bit ugly.

49:21 So these are the actual uh values for set one set set 0 set z one set z um I'm assuming here this representation to be general uh this is if all the roots are unique or are distinct. So there's no multiple roots.

50:01 In principle you could have a polomial with a factor is set. So what this means is is just the roots you can rewrite the polomial this is the same as the product of these three terms. Maybe I should have said this at the get-go.

50:27 uh you can just uh always write a polomial as factors of this form but maybe in general you need powers of these it could be a power of two here for some polomials um the nicer form of the partial fractions you get if the roots are distinct now in this case what's ugly about the roots is two things first of all there's no nice short representation there's some algebra algebraic numbers you can write them using roots uh square roots and so on but they're not nice rational numbers. So there's only an approximate solution given here plus in general there are complex numbers because you might have square root of minus of negative numbers in there but they're distinct. You see there's a um a real root 0.68 and there's two complex roots with um their complex conjugates. One is positive uh imaginary part, the other is negative imaginary part. But they're distinct. There are three distinct numbers.

51:29 Um also they're shown here. This is actually useful for another another bit that we'll come to later. Um here the three numbers are shown on the complex plane. And you see that this one is the one um of largest modulus I guess.

51:55 I have smallest modulus. This is closer to zero than these two that's hardly visible. Okay. Now in nice examples you can now solve for A, B and C and um just insert these. In general, you get this um if you rewrite the left hand side using this product, you can solve for a, b and c just by multiplying through some of these uh factors and setting set to uh specific values and then you can compute the explicit numbers for a, b and c. Now in this case this will involve all these uh complex algebraic numbers. So it's not going to look nice and we might not do it because we don't have to. The point is that this always has a a nice form. So if we take the first one, this is almost one of the formulas that we had on the cheat sheet. Maybe that's the easiest to see.

53:11 is the generalization of the one we used before of this shape 1 / 1 minus some constant times zed. And what we have is close enough to that that we have a hope to get it into that shape by massaging terms a bit.

53:41 So we try to get it in that shape. Well, we can divide by set in the pull set out here. Um what do we do?

53:50 We uh divide by one. And now we have it in this form. the constant is is one over Z and we have some factor in front but that's actually just a factor you can pull out. So [Music] um if you if you look at the representation for our generating function all the way at the very beginning if you multiply each of the sequence uh entries by two you can pull out the two of the sum and you get two in front of the generating function. So multiplying the generating function by a constant multiplies each of the sequence um entries by the same constant. So multiplying by a constant as we do it uh with this minus a over zero that's going through all the way to uh coefficients. So we can uh formally we can say we take the coefficient of this a this term a divided z minus zero. That's the same as taking coefficients on on this thing because they're the same functions. But also it means I can pull out this factor a over zero and then take coefficients of what's left. namely this part with a one. Okay. And now I'm using that this has the form if I said z to 1 / z I get that it has this closed form. So uh taking the coefficient just gives me a c to the power i. So the coefficient here is this thing as before and then that becomes just 1 / z0 to the power k the power we extract.

56:17 Okay we'd have to do this for the other sumance but that's another cool property of generating function of generating functions. If you have a sequence where bk is the sum of two sequences ak plus ck then also the generating functions add up because you can split the sum for the two parts. So a second property that we're using here plugging coefficients in b of set the actual thing we want is plugging the coefficients in this plus the coefficient of this plus the coefficient of this. Okay. Um so let me uh sketch this. Our BK the answer we want is the coefficient of B of Z by definition and that's going to split into terms of this form for A, B and C. Uh so it's essentially this term 1 / z to the k. Then we have the same for b and for c where I'm just replacing what the um constants and out of time. 1 over C2. Okay. Now, what does that help us?

57:57 First of all, it's a closed form representation. It has some annoying constants that you really only want to deal with with computer algebra. Um, but they're in principle computable. These are just constants that come out of the partial fraction the partial fraction uh representation for this for this rational function and the roots of a polomial. These are easy to if you just want to get numbers you can easily approximate them. But the second thing is these are simple functions. They're all pol they're all exponential functions. Right? This is some number to the K, some number to the K, some number to the K and then a linear combination for large K. What will happen for large K? Only the one with the largest uh expo uh the largest base of the exponential growth will will be relevant. The others are exponentially smaller in the literal sense of the term. So this will be asmtoically the same or let's let's get rid of the constants in the same same way.

59:09 Um and let's say it's uh it's just one over zero is the one that has the largest absolute value. Uh let me let me write it like this. Uh come on a lot of calculations. Assuming that the absolute value of this uh of this root is larger than the absolute values of the others. I guess uh smaller. You want the the reciprocals to be larger. The one that has the largest reciprocal is the one that dominates the growth and that's the one that has the large smallest absolute value. Right? Okay. So you take these three roots and you find that this one is going to have the uh smallest absolute value. You would have to compute the square these two, add them up and take the square root. um whatever that works out to. Um but this one's going to be the dominating factor. Uh we could try to do that, but maybe in the interest of time, let's not do it. So one over this number is the exponential growth of B or BK. Okay.

1:01:14 and I guess there's no there's no way to do this without keyboard. Okay, let me at least get the number. So uh one over this one 0 68233. Yeah. Okay. Uh if you want to copy out then you have to pay their subscription. So it's 1.465. That's what I wanted to uh note down.

1:01:58 So what's the point of all of this? The exponential growth of the cost of our of our running time here of BK is going to be this 1.4 four six whatever to the power k and that's substantially better than 2 to the k right you can plug in some numbers maybe this algorithm is still doable for k equals uh I don't know 50 whereas 2 to the k maybe 20 at best but we bought a bit bit of uh larger sizes we can deal Good. Uh to wrap this up, you can um do the whole uh analysis we've done in general if you have any recurrence of this form in the general case. And I'm just writing this down so you don't have to always go through generating functions. uh if you design algorithms where you have this this structure you recurse on different parts and the sizes of the parameters drop by different amounts DI uh you can immediately just invoke this result um in general you can explicitly give the TN in terms of some constants and powers um but basically it's the same same problem you get a polomial and you have to take the roots of that polomial um And uh what we'll what we'll usually use is just this uh corollery there's the power uh the the exponential growth is the root here is a different polomial. So here is actually largest absolute value of the root and the factor the polomial factor is the multiplicity of the root. So you can uh shortcut all the generating function fun um to just this uh this final result here.

1:03:59 And if we do that in our case instead of three slides of calculations you just take this polomial from the theorem and plug in the numbers. So our the characteristic vector here is one and three because we make the parameter smaller by one and three respectively. So we get this and we solve for the uh the roots here and you get the same ugly numbers of course.

1:04:32 Okay, so that's what we've proven uh for the total time same is true and uh yeah the polinomial time is not so important but now we've reduced the exponential growth substantially and you know how to analyze these sequences.