1 00:00:00,025 --> 00:00:04,977 The guarantees states that if you implement a union-find data structure 2 00:00:04,977 --> 00:00:08,492 using lazy unions, union by rank, and path impression, 3 00:00:08,492 --> 00:00:11,023 then you get a pretty amazing guarantee. 4 00:00:11,023 --> 00:00:15,030 Do any sequence you want of m union and find operations. 5 00:00:15,030 --> 00:00:18,810 The tool that I worked on, that is data structures, is bound and above by 6 00:00:18,810 --> 00:00:22,330 times log star of n, where n is the number of objects in the data structure. 7 00:00:23,840 --> 00:00:26,960 So on the one hand I hope you're suitably impressed by this result. 8 00:00:26,960 --> 00:00:31,480 So the proof of it that we gave in the last video is frankly totally brilliant. 9 00:00:31,480 --> 00:00:33,970 And secondly the guarantee itself is excellent, what with 10 00:00:33,970 --> 00:00:38,380 log star of n being bounded above by five for any imaginable value of n. 11 00:00:40,770 --> 00:00:44,730 On the other hand, I do hope there's sort of a little voice inside you wondering if 12 00:00:44,730 --> 00:00:48,130 this log star bound could really be optimal. 13 00:00:48,130 --> 00:00:51,330 Can we do better maybe by a sharper analysis of the data structure 14 00:00:51,330 --> 00:00:54,170 we've been discussing, or perhaps by adding further ingenuity, 15 00:00:54,170 --> 00:00:56,880 further optimizations to the data structure? 16 00:00:56,880 --> 00:00:59,740 For all we know, you might be able to get away with a linear amount of work. 17 00:00:59,740 --> 00:01:04,131 So O of M worked to process an arbitrary sequence of finds and unions. 18 00:01:05,438 --> 00:01:08,910 It turns out you can do better than the guarantee. 19 00:01:08,910 --> 00:01:12,750 There is a sharper analysis of the exact same data structure. 20 00:01:12,750 --> 00:01:17,280 That analysis was given by Tarjan, and here is the statement of his guarantee. 21 00:01:19,340 --> 00:01:23,090 So the improved bound states that for an arbitrary sequence of m union and 22 00:01:23,090 --> 00:01:27,250 find operations, the total work done by this data structure union by rank and 23 00:01:27,250 --> 00:01:32,140 path compression, is big O of m times alpha of n. 24 00:01:32,140 --> 00:01:34,340 Now what, you may ask, is alpha of n? 25 00:01:34,340 --> 00:01:37,450 That's a function known as the inverse Ackermann function. 26 00:01:39,490 --> 00:01:42,050 So what then is the inverse Ackermann function? 27 00:01:42,050 --> 00:01:44,800 Well the short answer is that it's a function that, 28 00:01:44,800 --> 00:01:48,940 incredibly, grows still more slowly, in fact, much, much, 29 00:01:48,940 --> 00:01:54,760 much more slowly, than the log star function we discussed in the bound. 30 00:01:54,760 --> 00:01:58,770 The precise definition is non-trivial, and that is the subject of this video. 31 00:01:58,770 --> 00:02:01,030 In the next video, we'll prove this theorem and 32 00:02:01,030 --> 00:02:04,000 explain how the inverse Ackerman function arises 33 00:02:04,000 --> 00:02:07,310 in an optimal analysis of union by rank with path compression. 34 00:02:09,142 --> 00:02:11,030 So I'll first define the Ackerman function, 35 00:02:11,030 --> 00:02:12,690 and then I'll describe its inverse. 36 00:02:12,690 --> 00:02:15,669 One thing I should warn you is you will see slight variations on these two 37 00:02:15,669 --> 00:02:17,550 definitions out there in the literature. 38 00:02:17,550 --> 00:02:20,530 Different authors define them in ways convenient for their own purposes. 39 00:02:20,530 --> 00:02:23,880 That's also what I'm going to do here, I'm going to take one particular definition 40 00:02:23,880 --> 00:02:26,570 convenient for the union find data structure analysis. 41 00:02:28,080 --> 00:02:31,506 All of the variants that you'll see out there in the literature exhibit roughly 42 00:02:31,506 --> 00:02:32,797 the same ridiculous growth. 43 00:02:32,797 --> 00:02:36,853 So the details aren't really important for the analysis of data structures and 44 00:02:36,853 --> 00:02:37,520 algorithms. 45 00:02:39,580 --> 00:02:42,350 So you can think of the Ackermann function as having two arguments, 46 00:02:42,350 --> 00:02:46,100 which I'm going to denote by k and r, both of these are integers. 47 00:02:46,100 --> 00:02:49,020 k should be at least zero, r should be at least one. 48 00:02:50,750 --> 00:02:53,220 The Ackermann function is defined recursively. 49 00:02:53,220 --> 00:02:55,950 The base case is when k equals zero. 50 00:02:55,950 --> 00:03:00,160 For all r, we define a sub zero of r as the successor function, 51 00:03:00,160 --> 00:03:03,060 that is it takes its input r and it outputs r plus one. 52 00:03:05,010 --> 00:03:08,433 In general, when k is strictly positive, 53 00:03:08,433 --> 00:03:13,378 the argument r tells you how many times to apply the operator, 54 00:03:13,378 --> 00:03:17,675 the function a k minus 1, starting from the input r. 55 00:03:20,570 --> 00:03:24,080 That is, it's the r fold composition of a sub k minus 1. 56 00:03:24,080 --> 00:03:29,066 And again applied to the argument r. 57 00:03:29,066 --> 00:03:31,660 So in some sense describing the algorithm function isn't that hard right? 58 00:03:31,660 --> 00:03:35,831 I didn't really need that much of a slide to actually write down its description, 59 00:03:35,831 --> 00:03:39,930 but getting a feel for what on earth this function is, takes some work. 60 00:03:39,930 --> 00:03:40,640 So the first thing, 61 00:03:40,640 --> 00:03:44,030 maybe this is a sanity check, is note that it is a well-defined function. 62 00:03:44,030 --> 00:03:45,460 So, you know, you're all programmers, so 63 00:03:45,460 --> 00:03:49,040 you could easily imagine writing a program which took as input, k and 64 00:03:49,040 --> 00:03:53,490 r, and at least in principle, given enough time, computed this number. 65 00:03:53,490 --> 00:03:56,100 It would be a very simple recursive algorithm with a pseudo-code just 66 00:03:56,100 --> 00:03:57,700 following the mathematical definition. 67 00:03:57,700 --> 00:04:00,400 So it is some function, given k and r, 68 00:04:00,400 --> 00:04:04,370 there is some number that's the result of this definition. 69 00:04:04,370 --> 00:04:07,310 Now, in the next sequence of quizzes, let's get a feel for 70 00:04:07,310 --> 00:04:09,500 exactly how this function behaves. 71 00:04:11,740 --> 00:04:15,780 And so let's start on the first quiz by fixing k to be one. 72 00:04:15,780 --> 00:04:18,340 And now, viewing the Ackermann function with k fixed at one, 73 00:04:18,340 --> 00:04:20,450 is a function purely of r. 74 00:04:20,450 --> 00:04:24,389 So, what function does a1 of r correspond to. 75 00:04:30,752 --> 00:04:35,430 All right, so the correct answer is b, at least a1 is quite simple to understand. 76 00:04:35,430 --> 00:04:36,760 All it does is double the argument. 77 00:04:36,760 --> 00:04:38,810 So if you give it r, it's going to spit out 2r. 78 00:04:40,280 --> 00:04:41,030 So, why is that? 79 00:04:41,030 --> 00:04:47,130 Well, any one of our by definition is just the function a0 applied to r, 80 00:04:47,130 --> 00:04:52,130 r times, a0 by definition is the successor function as one, so if you 81 00:04:52,130 --> 00:04:56,830 apply the successor function r times, starting from r you get 2r as a result. 82 00:04:58,620 --> 00:05:01,020 So let's now move from a1 to a2. 83 00:05:01,020 --> 00:05:04,540 So let's think about exactly the same question, fixing k at 2 and 84 00:05:04,540 --> 00:05:07,400 regarding it as a function of r only. 85 00:05:07,400 --> 00:05:08,700 What function is it? 86 00:05:19,347 --> 00:05:20,871 So answer here is c for 87 00:05:20,871 --> 00:05:25,460 every positive integer are a2 of r is equal to r times 2 to the r. 88 00:05:27,780 --> 00:05:29,390 And the reasoning is the same as before. 89 00:05:29,390 --> 00:05:33,292 So remember a2 of r just means you apply a1 r times. 90 00:05:33,292 --> 00:05:36,060 In the last quiz we discovered that a1 was doubling. 91 00:05:36,060 --> 00:05:37,780 So if you double r times, 92 00:05:37,780 --> 00:05:40,240 it has the effect of multiplying by a 2 to the r factor. 93 00:05:42,410 --> 00:05:44,010 So let's take it up a notch yet again. 94 00:05:44,010 --> 00:05:47,260 Let's bump up k to three and let's think about A sub 3. 95 00:05:47,260 --> 00:05:51,860 But let's not yet think about exactly what a sub 3 is as a function of r. 96 00:05:51,860 --> 00:05:52,760 Let's keep things simple. 97 00:05:52,760 --> 00:05:56,533 What is just a sub 3 evaluated when r equals 2? 98 00:05:56,533 --> 00:05:59,500 So k equals 3, r equals 2, that's a number. 99 00:05:59,500 --> 00:06:00,370 What number is it? 100 00:06:06,090 --> 00:06:08,630 Okay, so the correct answer is the third one. 101 00:06:08,630 --> 00:06:11,150 It's 2048, also known as 2 to the 11th. 102 00:06:14,010 --> 00:06:21,494 Let's see why, well a sub 3 of 2 that just means we apply a sub 2 twice to 2. 103 00:06:21,494 --> 00:06:24,851 Now in the last quiz we evaluated not only a sub 2 of 2 but 104 00:06:24,851 --> 00:06:26,430 a sub 2 of all integers r. 105 00:06:26,430 --> 00:06:29,395 We discovered that it's r times 2 to the r. 106 00:06:29,395 --> 00:06:33,122 So that means that it's a simple matter to evaluate this 107 00:06:33,122 --> 00:06:35,200 application of a sub 2 twice. 108 00:06:35,200 --> 00:06:38,670 First a sub 2 of 2 that's just 2 times 2 to the 2 that's just 8. 109 00:06:40,420 --> 00:06:44,141 Then a sub 2 of 8 is going to be 8 times 2 to the 8, also known as 2 to the 11 or 110 00:06:44,141 --> 00:06:44,710 2048. 111 00:06:49,144 --> 00:06:50,179 So what about in general? 112 00:06:50,179 --> 00:06:54,920 How does the function a sub 3 behave as a function of a general parameter r? 113 00:06:54,920 --> 00:06:58,050 When we answer this question we're going to see for the first time 114 00:06:58,050 --> 00:07:02,440 the ridiculously explosive growth that the Ackerman function exhibits and 115 00:07:02,440 --> 00:07:03,880 this will just be the tip of the iceberg right? 116 00:07:03,880 --> 00:07:07,071 This is just when k equals 3. 117 00:07:07,071 --> 00:07:09,943 So by definition a sub 3 of r you start from r and 118 00:07:09,943 --> 00:07:12,630 you apply the function a sub 2 r times. 119 00:07:12,630 --> 00:07:15,230 So let's remind ourselves what the function a sub 2 is. 120 00:07:15,230 --> 00:07:16,660 We computed that exactly. 121 00:07:16,660 --> 00:07:18,880 That's r times 2 to the r. 122 00:07:18,880 --> 00:07:22,760 So to make out life simple, let's just think about the 2 to the r part. 123 00:07:22,760 --> 00:07:24,050 So in the real function a sub 2, 124 00:07:24,050 --> 00:07:27,670 you also multiply by r, but let's just think about the 2 to the r part. 125 00:07:27,670 --> 00:07:31,000 So imagine you applied that function over and over and over again. 126 00:07:31,000 --> 00:07:32,140 What would you get? 127 00:07:32,140 --> 00:07:34,740 Well now you get a tower of 2's where 128 00:07:34,740 --> 00:07:38,820 the height of the tower is the number of times that you apply that function. 129 00:07:38,820 --> 00:07:43,040 But if you apply it once, you get 2 to the r, If you apply it twice you're going to 130 00:07:43,040 --> 00:07:49,600 get two raised to the 2 to the r, 3 times 2 to 2 to the 2 of the r and so on. 131 00:07:49,600 --> 00:07:54,420 So all applications of a sub 2 gives you something that's even bigger than a tower 132 00:07:54,420 --> 00:07:55,150 of r2's. 133 00:07:57,660 --> 00:07:59,570 So, let's move on to a4, and 134 00:07:59,570 --> 00:08:03,490 this is the point in which personally my brain begins to hurt. 135 00:08:03,490 --> 00:08:05,500 But let's just push a little bit further so 136 00:08:05,500 --> 00:08:08,880 that we appreciate the ridiculous growth of the Ackermann function. 137 00:08:11,130 --> 00:08:15,010 And as with a3, let's punt for the moment on understanding the dependence for 138 00:08:15,010 --> 00:08:15,710 a general r. 139 00:08:15,710 --> 00:08:18,300 Let's just figure out what a sub 4 of 2 is. 140 00:08:18,300 --> 00:08:20,600 So, k equals 4, r equals 2. 141 00:08:20,600 --> 00:08:25,567 Well, so this by definition, you just take 2 and you apply a sub 3 twice. 142 00:08:25,567 --> 00:08:30,400 We computed a sub three of 2 in the previous quiz. 143 00:08:30,400 --> 00:08:31,850 We discovered that was 2,048. 144 00:08:31,850 --> 00:08:35,044 So that's the result of the first application of a3. 145 00:08:36,486 --> 00:08:41,590 And now we find ourselves applying a3 to 2048, so in effect r now is 2048. 146 00:08:41,590 --> 00:08:45,816 And remember we concluded the last slide by saying well a sub 3, 147 00:08:45,816 --> 00:08:49,663 whatever it is, it's at least as big as a tower of r2's. 148 00:08:49,663 --> 00:08:52,299 And here r is 2048. 149 00:08:53,590 --> 00:08:56,770 So, this of course now is the land of truly ridiculous numbers that we're 150 00:08:56,770 --> 00:08:57,320 dealing with. 151 00:08:57,320 --> 00:08:59,650 I encourage you to take a calculator or computer and 152 00:08:59,650 --> 00:09:02,440 see how big of a tower of 2's you can compute, and 153 00:09:02,440 --> 00:09:07,748 it's not going to be anywhere close to 2,000, I can promise you that. 154 00:09:07,748 --> 00:09:12,690 And hey that is just a4 of 2, what about the function a4 for a general value of r? 155 00:09:14,750 --> 00:09:16,160 Well, of course, in general, 156 00:09:16,160 --> 00:09:20,040 a4 of r is going to be r applications of a3 starting at r. 157 00:09:20,040 --> 00:09:23,200 Now, in the last slide, 158 00:09:23,200 --> 00:09:27,568 we argued that a sub 3, this function is bounded below by a tower function. 159 00:09:27,568 --> 00:09:29,965 So a sub 3 takes in some input, some integer, 160 00:09:29,965 --> 00:09:33,284 and it spits out some tower with height equal to that integer, so 161 00:09:33,284 --> 00:09:36,868 what happens when apply that tower function a3 over and over again? 162 00:09:36,868 --> 00:09:40,690 Now you get what's called an iterated tower function. 163 00:09:42,990 --> 00:09:47,029 So when you apply the function a sub 3 for the time the r is going to spit out 164 00:09:47,029 --> 00:09:51,846 a number which is bounded below by a tower of height r, tower of 2's, all of them. 165 00:09:51,846 --> 00:09:57,165 Now we apply a3 a second time, it's output is going to be a tower of 2's, 166 00:09:57,165 --> 00:10:02,240 whose height is lowerbounded by a tower of 2's of height r, and so on. 167 00:10:02,240 --> 00:10:07,672 Every time you apply a sub 3, you're just going to iterate this tower function. 168 00:10:07,672 --> 00:10:12,490 You will sometimes see the iterated tower function referred to as a yowzer function. 169 00:10:12,490 --> 00:10:14,560 You probably think I'm pulling your leg, but I'm not kidding. 170 00:10:14,560 --> 00:10:15,060 You can look it up. 171 00:10:17,749 --> 00:10:19,669 So that is the Ackerman function and 172 00:10:19,669 --> 00:10:24,030 a bunch of examples to appreciate just how ridiculously quickly it is growing. 173 00:10:24,030 --> 00:10:26,530 So now let's move on to define its inverse. 174 00:10:26,530 --> 00:10:30,550 Now that Ackerman function has two parameters k and r excuse me. 175 00:10:30,550 --> 00:10:32,380 So to define an inverse I'm going to fix one of those. 176 00:10:32,380 --> 00:10:35,293 Specifically I'm going to fix r equal to 2. 177 00:10:37,229 --> 00:10:39,830 So the inverse Ackermann function is going to be denoted by alpha. 178 00:10:39,830 --> 00:10:45,348 For simplicity, I'll define it only for values of n that are at least 4 and 179 00:10:45,348 --> 00:10:49,289 it's defined for giving value of n as the smallest k so 180 00:10:49,289 --> 00:10:54,823 that if you apply a sub k to 2, to r equals 2, then the result is at least n. 181 00:10:57,138 --> 00:11:00,009 So again it's simple enough to kind of write down a definition like this, but 182 00:11:00,009 --> 00:11:03,600 you really have to plug in some concrete numbers to get a feel for what's going on. 183 00:11:03,600 --> 00:11:05,090 So lets just write out, you know, 184 00:11:05,090 --> 00:11:08,150 what are the values of n that will give you alpha of n equal 1. 185 00:11:08,150 --> 00:11:10,900 That will give you alpha of n equal 2, alpha of n equal 3, and so on. 186 00:11:13,080 --> 00:11:17,606 Okay so for starters, alpha of 4 is going to be equal to 1, right. 187 00:11:17,606 --> 00:11:22,237 So if you applied a 0 to 2, that's the successor function so you only get 3, so 188 00:11:22,237 --> 00:11:24,158 that's not at least as big as 4. 189 00:11:24,158 --> 00:11:27,024 On the other hand, if you apply a sub 1 to 2, 190 00:11:27,024 --> 00:11:31,260 that's the doubling function, so if you apply it to 2 you get 4. 191 00:11:31,260 --> 00:11:37,036 So a sub 1 does give you a number which is at least as big as n when n is 4. 192 00:11:37,036 --> 00:11:39,374 So next I claim that the values of n for 193 00:11:39,374 --> 00:11:43,240 which alpha of n equals two are the values 5, 6, 7 and 8. 194 00:11:43,240 --> 00:11:44,090 Why is that true? 195 00:11:44,090 --> 00:11:47,130 Well, if you start from 2 and you apply the function a sub 1, 196 00:11:47,130 --> 00:11:49,310 the doubling function you only get 4. 197 00:11:49,310 --> 00:11:52,890 So, a sub 1 is not sufficient to achieve these values of n's. 198 00:11:52,890 --> 00:11:55,577 On the other hand if you apply a sub 2 to 2, 199 00:11:55,577 --> 00:12:00,356 remember that's the function which given an r outputs r times 2 to the r, so 200 00:12:00,356 --> 00:12:04,788 when you apply it to 2, you get 2 times 2 to the 2, also known as 8. 201 00:12:04,788 --> 00:12:09,075 So a sub 2 is sufficient to map 2 to a number at least as big as 8. 202 00:12:11,110 --> 00:12:14,805 By the same reasoning, recall that we computed a sub 3 of 2 and 203 00:12:14,805 --> 00:12:16,777 we computed that to be 2048. 204 00:12:16,777 --> 00:12:21,174 So therefore for all of the bigger values of n starting at 9 and going all the way 205 00:12:21,174 --> 00:12:24,902 up to 2048, their alpha value is going to be equal to 3 because that is 206 00:12:24,902 --> 00:12:28,990 the smallest value of k such that a sub k of 2 is at least those values of n. 207 00:12:31,060 --> 00:12:33,430 And then things start getting a little bit ridiculous. 208 00:12:33,430 --> 00:12:36,930 So remember we also lower bounded a sub 4 of 2. 209 00:12:36,930 --> 00:12:41,330 We said that's at least a tower of 2's of height 2048. 210 00:12:41,330 --> 00:12:46,430 So for any n up to that value, up to a tower of 2's of height 2048, 211 00:12:46,430 --> 00:12:49,730 alpha of those n's is going to be equal to 4. 212 00:12:52,300 --> 00:12:54,800 This of course implies that the inverse Ackermann 213 00:12:54,800 --> 00:12:58,820 function value of any imaginable number is at most 4. 214 00:12:58,820 --> 00:13:03,100 And I don't know about you, but my brain is already hurting too much to think about 215 00:13:03,100 --> 00:13:06,175 which of the values of n, such that alpha is equal to 5. 216 00:13:09,329 --> 00:13:14,030 So as a point of contrast, let's do the same experiment for the log star function, 217 00:13:14,030 --> 00:13:18,597 so that we get some appreciation about how as glacially growing a log star may be, 218 00:13:18,597 --> 00:13:22,790 the inverse Ackermann function is growing still qualitatively slower. 219 00:13:24,800 --> 00:13:27,730 So the log star function remember is the iterated logarithm, so 220 00:13:27,730 --> 00:13:31,210 it's starting from n how many times you need to hit log in your calculator, 221 00:13:31,210 --> 00:13:34,575 let's say base two before the result drops below 1. 222 00:13:36,940 --> 00:13:38,900 So when is log star n going to be equal to 1? 223 00:13:38,900 --> 00:13:40,610 Well that's when n is going to be equal to 2. 224 00:13:40,610 --> 00:13:42,900 Then you hit log once and you drop from 2 to 1 and you're done. 225 00:13:45,050 --> 00:13:49,355 If n equals 3 of 4 then you need more than one application of logarithm to drop below 226 00:13:49,355 --> 00:13:53,110 1, but you only need two applications, so log star of n is going to be 2 for 227 00:13:53,110 --> 00:13:53,980 n equals 3 and 4. 228 00:13:56,390 --> 00:14:01,260 Similarly for n anywhere between 5 and 16 log star n is going to be equal to 3. 229 00:14:01,260 --> 00:14:05,861 Right if we start from 16 that's 2 to the 4, so if you fly a log once you get 4, 230 00:14:05,861 --> 00:14:08,667 a second time you get 2, a third time you get 1. 231 00:14:11,934 --> 00:14:16,460 By analogy, the values of n for which the log star of n equals 4 are going to be 232 00:14:16,460 --> 00:14:20,989 starting at 17 and going up to 2 to the 16, also known as 65536. 233 00:14:23,790 --> 00:14:27,339 So let's just go one more step for which n is log star of n equal to 5. 234 00:14:27,339 --> 00:14:32,037 Well obviously we start at 65537, and we end at 2 raised to 235 00:14:32,037 --> 00:14:37,519 the largest number of the previous block, so 2 raised to the 65536. 236 00:14:39,460 --> 00:14:42,390 So, these numbers are impressive enough on the right hand side, but there is no 237 00:14:42,390 --> 00:14:46,675 imaginable number of importance for which log star is going to be bigger than 5. 238 00:14:48,210 --> 00:14:51,000 Looking at the left and the right hand sides though, we see that there really 239 00:14:51,000 --> 00:14:54,840 is a qualitative difference between the rate of growth of these two functions. 240 00:14:54,840 --> 00:14:56,060 With the inverse Ackermann function, 241 00:14:56,060 --> 00:14:59,461 in fact, growing much, much slower than the log star function. 242 00:15:01,100 --> 00:15:04,030 So perhaps the easiest way to see that is to look at the right hand side, and 243 00:15:04,030 --> 00:15:07,710 on each of the lines in the right hand side, look at the largest value of n, so 244 00:15:07,710 --> 00:15:09,610 that log star is a given number. 245 00:15:09,610 --> 00:15:13,435 So for example, in the third line, the largest n such that log star of n equals 246 00:15:13,435 --> 00:15:19,310 3, is a tower of 2s of height three, 2 to the 2, to the 2, also known as 16. 247 00:15:19,310 --> 00:15:20,862 Similarly on the fourth and 248 00:15:20,862 --> 00:15:24,507 fifth lines the largest n to give values of log star equal to 4 and 249 00:15:24,507 --> 00:15:28,438 5 are a tower of 2s of height 4 and two and a tower of 2s of height 5. 250 00:15:28,438 --> 00:15:33,040 On the other hand look at the fourth line on the left hand side. 251 00:15:33,040 --> 00:15:36,740 So I really when we ask for the largest values of n that have inverse Ackermann 252 00:15:36,740 --> 00:15:40,970 value 4, we're talking about towers of 2s, in fact of height 2048. 253 00:15:40,970 --> 00:15:45,620 So that is the n's which give us alpha of n equal to 4. 254 00:15:45,620 --> 00:15:50,152 We would have to write down 2048 lines on the right hand side before we had values 255 00:15:50,152 --> 00:15:51,650 of n that were equally big. 256 00:15:53,866 --> 00:15:58,161 This indicates how the log star function while growing glacially indeed, 257 00:15:58,161 --> 00:16:02,455 as it never the less moving at light speed compared to the inverse Ackermann 258 00:16:02,455 --> 00:16:03,150 function.