> LeekScript Tutorial
Warning: This article is mathematically intensive (at least for this wiki). Do not use without medical advice.
More seriously: here I'm going to try to talk about the optimization of recursive functions (Recursion in depth). This article is aimed more at people who are interested in functional programming and in programming theory.
When you write a recursive function, it isn't always easy to know how many calls it will make before reaching the result. Or even, sometimes, whether it will reach the result at all. The recursion tutorial gives some ways to optimize recursive functions, but doesn't study their complexity or their correctness, so here I'll use examples to illustrate a few methods for working these out.
This list of examples is not meant to be exhaustive: for each of your algorithms, you'll have to look closely at the operations it performs.
It's then up to you to reuse these ideas in your own algorithms, and if you find other examples worth mentioning, explain them here!
Some simple recursive functions have a complexity that is easy to study. This is the case of the first example in the recursion tutorial:
function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }
Here it's quite simple: you can easily see that if you give this function a (positive!) integer n, it will add n to the sum from 0 to n-1, which it computes by calling itself. So it computes n + (n-1 + ... + (0)...), which makes n additions and n function calls, i.e. a complexity of O(n).
However, if you give it a negative integer as input, this function will cause a stack overflow: it will keep adding negative numbers without ever reaching 0. Likewise, if you give it a non-integer number, subtracting 1 over and over will never reach 0. So pay attention to the correctness of your recursive functions: if you haven't planned for every case, or if you use them with an input that doesn't match what you had in mind when you wrote them, you could be in for some nasty surprises.
The tutorial on the complexity of an algorithm, for its part, gives the example of a function with complexity O(2^n):
function getAllCombos(item_list){ var nb_items = count(item_list);
if(nb_items == 1) { return [[], item_list]; }
var sub_list = subArray(item_list, 1, nb_items - 1); var partial_combos = getAllCombos(sub_list); // Recursive call var m = count(partial_combos);
//Then we duplicate the list of combos: we keep the ones we had, and add the same ones with the first element of item_list for(var i=0; i P(n) = 2*P(n-1). Since we also have P(1) = 2, we get the formula P(n) = 2 * ... * 2 = 2^n, hence the (at least) exponential complexity. We can then show that this function's complexity is indeed exponential (and no worse): each call to the function creates an array of size n-1 with subArray (cost: O(n)), then does m pushes, where m is the size of the array of partial combos, i.e. 2^(n-1) (cost: K * 2^(n-1), where K is the cost of a push), which dwarfs the cost of the subArray, so the complexity is determined by the number P(n) of pushes performed.
This is the idea I'm going to develop here: find a recurrence formula and try to derive from it a formula giving an upper bound on the number of calls, then finally deduce the complexity by looking at what the function does besides its recursive calls. I won't talk much about correctness from now on (except at the very end), but keep the notion in mind...
From now on, C(n) denotes the cost of the function being studied.
The word "simple" here doesn't mean that the complexity will be nice, or even necessarily easy to compute. It means that we have a first-order recurrence, that is, an expression giving C(n) in terms of C(n-1).
Let's start gently. The first example I'm going to study is rather silly, but it also lets me introduce my notation. You won't learn anything mind-blowing about complexity here, but at least the simple cases will be covered on this page.
Let's take a very simple function (useless, and rather badly written since it makes the same function call twice, but I needed a simple example):
function sumPowers(n , k) { //n integer, k any number if (n === 0) { return 0; } else { return n**k + (sumPowers(n - 1 , k) + sumPowers(n - 1 , k))/2; } }
Here the cost C(n) is studied as a function of the integer n alone, since exponentiation has a fixed cost in LeekScript. For the cost as a function of the size of the input, that is, of the number of bits of n, you would have to add an exponential to the complexities. But the goal here is to study sequences of the form C(n) = a * C(n-1) + b, so I'll stick to the complexity as a function of n, not of its number of bits.
This function looks a lot like the first one we studied, but besides doing an addition, it also computes a power along the way. In LeekScript, the * operator costs 140 operations (just like the pow function), addition and subtraction cost 1, division costs 5, the if costs 1, the comparison n === 0 costs 1, and a function call with two arguments costs 5. So the cost function C(n) satisfies C(n) = 161 + 2C(n-1) for all n>0, and C(0)= 2.
Now let's ask ourselves how to estimate the cost from there. We have a sequence defined by a formula C(n) = a C(n-1)+ b and C(0) = c, with a ≠ 1. The idea is to bring it back to the form u(n) = a u(n-1), which is easier to work with. To do this, let u(n)=C(n) + b/(a-1). We can then write:
C(n) = a C(n-1) + b ⇒ C(n) = a C(n-1) + (a-1)b/(a-1) ⇒ C(n) = a C(n-1) + ab/(a-1) - b/(a-1) ⇒ C(n) + b/(a-1) = a C(n-1) + a*b/(a-1) ⇒ u(n) = a u(n-1)
So for all n >= 0, we have:
u(n) = a^n u(0)
Moreover, u(0) is easy to compute: u(0) = C(0) + b/(a-1) = c + b/(a-1). So we can deduce the value of u(n) for every n: u(n) = a^n * (c + b/(a-1)). Going back from u(n) to C(n) through the definition of u(n), we get:
C(n) = u(n) - b/(a-1) = a^n * (c + b/(a-1)) - b/(a-1)
It's not exactly a pretty formula, but what does it tell us? Well, that the cost is in O(a^n): b and c disappear into constants (multiplicative and additive ones). This function has an exponential cost with base a, which is 2 here. We could have guessed as much: what ends up being expensive is not computing the powers with , but stupidly recomputing the same things over and over. **Moral of the story: When you have a recursive function, never recompute anything that isn't needed!
And what if we had been smart and avoided recomputing?
function sumPowers(n , k) { //n integer, k any number if (n === 0) { return 0; } else { return n**k + sumPowers(n - 1 , k); } }
This time we would have had C(n) = 149 + C(n-1). So we get the case not covered by the above, where a = 1.
And this case is much simpler: by a straightforward induction, we get C(n) = 149n + C(0) = 149n + 2, hence a linear complexity, with a constant given by the cost of the operations performed in the loop.
If you've done a bit of math, you probably know what matrices are: arrays of numbers, with laws for addition, for multiplication by an element of the base field (let's say ℝ here), and for multiplication between matrices. We're going to look at computing the determinant of square matrices, a rather useful tool for studying them. Here is one way to compute this determinant:
function det(M){ //input M: square matrix of size n, as an array of size n containing arrays of size n that contain numbers. var n = count(M); if(n === 1) { return M[0][0]; // If the matrix has size 1, its determinant is equal to its only value } else { //Otherwise... var output = 0; var firstLine = shift(M);// ...we take the first row... for(var i=0; iC as a function of the number of rows of the matrix (or of the number of columns, which is the same thing since I took square matrices).
Cost for n = 1: not much, a few operations (note: count runs in constant time in LeekScript). Cost for n > 1:
So we have something of the form C(n) = n * C(n-1) + a * n^3 + some small stuff.
First, one thing we can say right away: C(n) > n * C(n-1). From this, we easily deduce that the complexity of this thing is at least of the order of n!, which is written Ω(n!).
In the other direction, we can also bound it from above: C(n) ⩽ n * C(n-1) + b * n^3 for some number b greater than a (and n large enough). Let's study the sequence defined by u(n) = n * u(n-1) + b * n^3 (for n>1) and u(1)=1 (u(1) isn't actually 1, but that won't change the complexity, only the constant hidden by the O). By induction, we have:
!Determinant_matrix_recurrence
The series of the terms i^2/((i-1)!) does converge to a finite limit. So we get u(n) ⩽ k * n! for some real number k. So C(n) has a complexity of at most O(n!). Together with what we had before, we conclude that C(n) has a complexity of O(n!).
This idea of trying to compare instead of writing an equality often turns out to be useful: after all, we're looking for an O(f(n)), not a precise estimate, and if we can say that the complexity is "at least this much" to show that a function is expensive, or "this much at worst" to show that it's cheap, that's already worth something!
These recurrences come up naturally when you use the bisection method (binary search) or divide-and-conquer algorithms. They generally lead to complexities involving logarithms.
LeekScript has a function for searching in an array. However, if you know that the array is sorted (because you sorted it beforehand, or because it's sorted by construction), there is a way to search faster than with that function:
function dichotomicSearchBetween(@array, i_min, i_max, @value){ //Input: a sorted array, the indices between which we search, and the value to look for // If we search between two equal indices, i.e. there is only one value to test: if ( i_min === i_max ) { if(array[i_min] === value) { return i_min; } else { return null; } } // Otherwise: we compute the middle index and search on one side or the other var i_mid = floor((i_max + i_min)/2); // If the value at this index in the array is the one we are looking for, we're done. if ( array[i_mid] === value ) { return i_mid; } // Otherwise, we check which side to search. if ( value C(n) = a + C(floor(n/2)) for n>1, and C(1) = a (we can use the same constant for both, even if it means replacing one of them with the larger of the two: it doesn't change the complexity, and it saves me from having two constants floating around). The question is then: how many times can you divide n by 2 before getting down to a size of 1? In other words, we're looking for k such that n/(2^k) = 1. This leads to n = 2^k, hence k = log(n) (where log is the base-2 logarithm). So we'll divide n by 2 at most log(n) times before reaching an array of size 1, which ends the chain of recursive calls.
So we'll go through at most log(n) steps. Since each step adds a cost of a, the cost of this function is a*log(n). The complexity of this algorithm is therefore O(log(n)) (or, for those who are wondering, O(ln(n)): logarithms are proportional to one another).
Be careful, though: this doesn't mean you should systematically sort all your arrays. While the cost of searching is reduced this way, the cost of sorting is O(n log(n)), which is more than the cost of searching with LeekScript's native function. If you have a lot of searches to do in an array, sorting it first can be a good idea; if you only have a few, it certainly isn't.
The merge sort algorithm is (as its name suggests) an algorithm for sorting an array. There are versions that use less memory, but they're a bit more complicated to implement than the one I'm going to show you below. As with any sorting algorithm, you can't hope for a better time complexity than O(n log(n)).
This algorithm relies on the following principle: if the array has size 1, it is necessarily sorted. Otherwise, you split the array in two, sort each half, and merge the two arrays to get a sorted array.
// Function that merges two sorted arrays while keeping the order function merge(@array1, @array2){ //Input: two sorted arrays var output = []; var l = count(array1), m = count(array2); var i = 0, j=0; //i and j keep track of how far we have got in each array while(i+j 1) makes two mergeSort calls on an input half the size, plus a merge of the two resulting arrays. Let's start by looking at the cost of merge. The merge function mainly consists of a big while loop over the sum of the sizes of the input arrays. So its complexity will be O(l+m), where l and m are the sizes of the input arrays. Since here we apply it to two arrays of size n/2, its complexity will be O(n). So we have a cost of the form C(n) = a + bn + 2C(n/2) for n>1, with a and b constants, and C(1) = a. Now let's count the number of steps: since the size is halved each time, we're looking for the number k such that n/(2^k)=1. As with binary search, this number is floor(log(n)), after which we reach the base case n=1.
Let's expand the resulting cost a little: C(n) = a + bn + 2C(n/2) = a + bn + 2(a + b*(n/2) + 2 * C(n/4)) = a + 2a + bn + bn + 4C(n/4). Since this repeats floor(log(n)) times before we reach the base case, we get a cost of C(n) = a(2^(floor(log(n))+1) - 1) + bnfloor(log(n)). Indeed, the sum of the 2^i * a for i going from 0 to floor(log(n)) is a * (2^(floor(log(n)) + 1) - 1).
Bounding floor(log(n)) from above by log(n), we get `C(n) array[b]){ //We swap the two end elements if they are in the wrong order var value = array[a]; array[a] = array[b]; array[b] = value; } if(b - a + 1 > 2){ // If the array has size > 2, we sort by thirds var t = (b - a + 1)/3; stoogeSortBetween(array, a, ceil(b - t)); stoogeSortBetween(array, floor(a + t), b); stoogeSortBetween(array, a, ceil(b - t)); } }
function stoogeSort(@array){ stoogeSortBetween(array, 0, count(array) - 1); }
var array = [2, 5, 8, 3, 4, 7, 6, 1, 9, 11, 10, 17]; stoogeSort(array); debug(array); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 17]
While this sort is simple to code (and has the good taste to be in place, that is, not to use up any memory), it is actually rather inefficient. To see why, let's count the recursive calls. Since the operations performed at each call (a possible swap, and a test on the length left to sort) don't depend on the length of the array, the number of operations will simply be a multiple of this number of calls. So I'll write C(n) for this number.
We have the following recurrence formula, since the function calls itself three times on 2/3 of the initial length: C(n) = 3 * C(2n/3). So to know how many times we'll have to multiply by 3, we need to find the number k such that (2/3)^k * n = 2, and we'll then have C(n) = 3^k * C(2) (and C(2) is just the number of operations needed to swap two elements).
This gives us n/2 = (3/2)^k, hence log(n/2) = k * log(3/2), i.e. k = log(n/2)/log(1.5). So we get C(n) = 3^(log(n/2)/log(1.5)) * C(2), which, after a little juggling with logarithms and exponentials, gives C(n) = (n/2)^(log(3)/log(1.5)) * C(2), hence C(n) = O(n^(log(3)/log(1.5))) ≈ O(n^2.71).
So the code has a polynomial complexity, but a higher one than a simple sort (such as insertion sort, which is in O(n^2)). In short, besides being intuitively more complicated, this sort is also slower than the simple sorts. It is, let's be honest, total garbage!
Exercise: the curious reader may wonder what happens if you try to sort by quarters, sorting groups of two quarters each time (just as we sorted groups of two thirds above). And you can go further: fifths, etc. In particular, notice that if you cut the array into k pieces with k>3, you have to sort more than k times, so you lose on the number of sorts per step, but gain on how much the arrays shrink at each step. Which classic sort do you get if you push this all the way to k = count(array)/2?
Unfortunately, the world isn't always as nice as above, and sometimes you get more complicated recurrences. The Fibonacci sequence is a classic example: the recursion tutorial showed you a way to reduce the complexity of the naive method I present below, but this situation can come up in other algorithms, so I'm going to work through this example.
The Fibonacci sequence is defined mathematically by u(0)=1, u(1)=1 and u(n) = u(n-1) + u(n-2) for n>1. Translated into code, this gives:
function fibonacci(n){ if(n 1, with n-1 and n-2 as arguments, we have C(n) = 2 + C(n-1) + C(n-2) (the calls to fibonacci(n-1) and fibonacci(n-2), plus the recursive calls that these two calls will trigger). Moreover, if n is 0 or 1, there are no recursive calls, so C(0) = 0 and C(1) = 0. Notice that the recurrence relation can be rewritten as C(n) + 2 = (C(n-1) + 2) + (C(n-2) + 2). So let u(n) = C(n) + 2, which leads us to study the sequence defined by:
u(0) = 2, u(1) = 2, and u(n) = u(n-1) + u(n-2) if n>1
Notice that this sequence is twice the Fibonacci sequence: the Fibonacci sequence very nearly gives its own cost.
Right, now we just have to study this thing. For that, I'll throw a theorem at you, and anyone who wants explanations is welcome to ask me on the game chat:
"Theorem: Let u(n) be a sequence in ℝ such that, for n > 1, u(n) = au(n-1) + bu(n-2). If a²+4b > 0, then there exist c and d in ℝ such that u(n) = c(x_1)^n + d(x_2)^n, where x_1 and x_2 are the roots of X²-aX-b. If a²+4b = 0, then there exist c and d in ℝ such that u(n) = (c + dn)(x_1)^n, where x_1 is the only root of X²-aX-b."
In our case, we have a = 1 and b = 1. The roots of X² - X - 1 are given by x_1 = (1+sqrt(5))/2 (what is known as the golden ratio) and x_2 = (1-sqrt(5))/2. So the theorem tells us that there exist c and d such that u(n) = c ((1+sqrt(5))/2)^n + d ((1-sqrt(5))/2)^n. Let's compute c and d using the values of u(0) and u(1):
2 = u(0) = c ((1+sqrt(5))/2)^0 + d ((1-sqrt(5))/2)^0 = c + d
2 = u(1) = c ((1+sqrt(5))/2) + d ((1-sqrt(5))/2)
After a bit of manipulation of these equations, we get:
c = 1 + 1/sqrt(5) and d = 1 - 1/sqrt(5)
So we have u(n) = (1 + 1/sqrt(5)) * ((1+sqrt(5))/2)^n + (1 - 1/sqrt(5)) * ((1-sqrt(5))/2)^n, and therefore, finally:
C(n) = (1 + 1/sqrt(5)) * ((1+sqrt(5))/2)^n + (1 - 1/sqrt(5)) * ((1-sqrt(5))/2)^n - 2.
OK, it's a pretty ugly formula because I detailed the calculations, but what matters here comes next. We could perfectly well have done without computing the constants for the complexity analysis!
Here is what remains to be noted: ((1-sqrt(5))/2)^n tends to 0 as n tends to infinity (because 0 ((1+sqrt(5))/2)^n tends to infinity as n tends to infinity (because 1 fibonacci function is O(((1+sqrt(5))/2)^n): written this way, the algorithm has an exponential complexity, whereas the recursion tutorial offers a linear-time algorithm. So it's important, when you're dealing with this kind of recurrence, to check whether a memoization or tail recursion technique could apply!
Incidentally, notice that in this particular case, we've done even better than that (take that, Pump, you can put your memoization away): we've given a constant-time algorithm to compute the value of the function (with a rounding error due to the use of floating-point numbers, admittedly, but nothing a round can't fix)!
function fibonacci(n){ return (1 + 1/sqrt(5))/2 * ((1+sqrt(5))/2)n + (1 - 1/sqrt(5))/2 * ((1-sqrt(5))/2)n; }
Now we're really getting into math. Fly, you fools!
I'm now going to present, through an example, a fairly powerful combinatorics technique for studying more complicated recurrence relations.
Suppose you have a map that looks like this one, with a horizontal gap of n cells between the blue and red cells (which makes a path of length 2n for our leek):
and that, for some mysterious reason, you want to find all the paths leading from the blue cell to the red cell that never go the wrong way, that is, never go back to the left (these are called Dyck paths). So at each step, there are two possible moves: down-right or up-right.
To do this, let's write a recursive algorithm that takes as input the number of downward and upward moves allowed (knowing that, since we start at the very top, we can only go up if we've gone down before):
function getDyckPathsAux(up, down){// up: the number of upward moves allowed, down: same for downward moves. if(up === 0 and down === 0){return ;} //If no moves are allowed any more, the only path left is the empty one. var paths = []; if(down>0){ for(var path in getDyckPathsAux(up+1, down-1)){//If we go down, we allow one more move back up push(paths, ["down"]+path); } } if(up>0){ for(var path in getDyckPathsAux(up-1, down)){//If we go up, it means we went down before push(paths, ["up"]+path); } } return paths; }
function getDyckPaths(n){ return getDyckPathsAux(0,n); }
getDyckPaths(3); // Gives down, down, down, up, up, up], [down, down, up, down, up, up], [down, down, up, up, down, up], [down, up, down, down, up, up], [down, up, down, up, down, up getDyckPaths(17); // Gives the paths from the blue cell to the red cell (well, it would, if it didn't blow way past the limit of one million operations per core)
The complexity of this function is hard to evaluate: sure, there are generally two choices (go down-right or go up-right), so you might think of an exponential complexity, but in reality the moves are forced as soon as you reach a green cell:
On a light green cell, you can only go up, and on a dark green cell, you can only go down.
So we're going to count the number of possible paths to study the complexity. Let N(n) be the number of paths returned by getDyckPaths(n), that is, the number of paths that always go right between two cells on the same row, n cells apart.
If n = 0, there is only one path: the empty path (the one that stays put). Otherwise, there are two possible cases for each path: either it comes back to the line between the start and the end (before reaching the end), or it doesn't.
If it doesn't, look at the line just below the one joining the start and end cells: the path starts by going down, then never goes back above this second line (otherwise it would come back to the first line), and ends by going up.
In this case, we're back to counting the Dyck paths between the light blue cell and the pink cell: there are N(n-1) possibilities.
If it does come back to the first line, it may do so several times. Let k be the largest integer such that the path reaches the first line after 2k steps (you have to go up and down the same number of times to get back to the same level, hence the form 2k). We can then split the path into two smaller Dyck paths:
If we require the path to go through the purple cell, we end up with two Dyck paths: the one from the blue cell to the purple cell, and the one from the purple cell to the red cell. So there are N(k) possibilities for the first path and N(n-k-1) for the second (indeed, we took k as large as possible: between the purple and red cells, the path doesn't come back to the first line, so we're back to the previous case), which makes N(k)*N(n-k-1) in all.
So we can write: N(n) = N(n-1) + sum(N(k)N(n-k-1), k=1..n-1), which gives the recurrence formula N(n) = sum(N(k)N(n-k-1), k=0..n-1).
And now... we seem to be stuck. At first glance, this recurrence formula doesn't look handy at all: it involves a big sum and products. And that's where math comes in!
We're going to look at the following series (a formal one: I won't study its convergence): S(X) = sum(N(n) X^n, n=0..infinity). We then have:
Here we recognize (if we're used to it, admittedly) a convolution product, so we get:
So we're down to expressing S in terms of X using this relation. To do so, notice that S(X) satisfies a quadratic equation, with discriminant 1-4X. So we set S(X)= (1-sqrt(1-4X))/2X (we could show that the other solution doesn't work: its leading term would be 1/X, which messes everything up).
How do we get the values of N(n) from this? Well, thanks to a fabulous tool: the (power) series expansion. Here, we have:
Now, in this expansion, the coefficients are by definition the N(i). So we get the following fabulous formula: N(n) = (2n)!/((n+1)!n!). These numbers are known as the Catalan numbers.
We can directly deduce the complexity: each path found had to be built by adding as many elements as the length of the path, i.e. 2n. So the complexity will be O(2n * (2n)!/((n+1)!n!)) = O(4^n / sqrt(n)) (I'll spare you the calculations showing that these two O's are equivalent; for those who want to know, it follows from Stirling's formula). Compared with the exponential complexity we might have assumed at first, we've gained a factor of sqrt(n). It's not much, but it's better than nothing.
Contrary to what you might think from this example alone, the difficulty rarely lies in the "series expansion" part. What's hard is usually getting a functional or differential equation from the recurrence formula, then solving it. This tool is quite powerful, but sometimes requires strong math skills!
Phew. Well, you've had a glimpse of what you can run into when you study complexities a bit more precisely than "eeny, meeny, miny, moe, looks quadratic to me".
So now we can move on to complexities you won't run into!
Normally, you won't run into these cases, but that doesn't mean they don't exist! This section is just here to show that sometimes the complexity can be enormous; it's here more or less on principle: if you have an algorithm with this kind of complexity, you certainly won't be able to run it except on very small inputs.
This function was created by Ackermann (hence its name), mainly for theoretical reasons: historically, it's one of the first examples of a function that is not primitive recursive (along with the Sudan function).
function Ackermann(m,n){ if(m === 0) return n + 1; if(n === 0) return Ackermann(m - 1, 1); return Ackermann(m - 1, Ackermann(m, n - 1)); }
Well, what this function computes is far from obvious. It isn't even obvious why it necessarily stops. In fact, you can show that it stops by introducing a lexicographic order on pairs of integers: we say that (a,b)Ackermann(m, n - 1) is indeed a call with a smaller pair since n-1Ackermann(m - 1, Ackermann(m, n - 1)) is a call on a smaller pair since `m-1Ackermann(4,n) = 2^(2^(...)) - 3, with n iterations of the power: for a given m, the function repeats n times the operation it performed with m-1.
So what can we say about the complexity of the following function?
function A(n){ return Ackermann(n,n); }
First, notice that the only operation the function performs on what it returns is adding 1, when m is 0. For example, for A(2), the sequence of computations looks like this:
Ackermann(2,2) = Ackermann(1, Ackermann(2,1)) = Ackermann(1, Ackermann(1, Ackermann(2,0))) // Case n = 0 = Ackermann(1, Ackermann(1, Ackermann(1,1))) = Ackermann(1, Ackermann(1, Ackermann(0, Ackermann(1, 0)))) // Case n = 0 = Ackermann(1, Ackermann(1, Ackermann(0, Ackermann(0, 1)))) // Case m = 0 = Ackermann(1, Ackermann(1, Ackermann(0, 2))) // Ackermann(0,1) is 2, we substitute it: that's one addition. = Ackermann(1, Ackermann(1, 3)) //Ackermann(0,2) is 3, we substitute it: a second addition. = Ackermann(1, Ackermann(0, Ackermann(1,2))) = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(1,1)))) = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, Ackermann(1,0))))) // Case n = 0 = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, Ackermann(0,1))))) // Case m = 0 = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, 2)))) // Ackermann(0,1) is 2, we substitute it: third addition. = Ackermann(1, Ackermann(0, Ackermann(0, 3))) // Ackermann(0,2) is 3, we substitute it: fourth addition. = Ackermann(1, Ackermann(0, 4)) // Ackermann(0,3) is 4, we substitute it: fifth addition. = Ackermann(1, 5) // Ackermann(0,4) is 5, we substitute it: sixth addition. = Ackermann(0, Ackermann(1,4)) = Ackermann(0, Ackermann(0, Ackermann(1,3))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(1,2)))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(1,1))))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, Ackermann(1,0)))))) // Case n = 0 = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, Ackermann(0,1)))))) //Case m = 0: now we can do our additions! = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, 2))))) // Seventh addition = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, 3)))) // Eighth addition = Ackermann(0, Ackermann(0, Ackermann(0,4))) // Ninth addition = Ackermann(0, Ackermann(0, 5)) // Tenth addition = Ackermann(0, 6) // Eleventh addition = 7 // Twelfth addition, and the computation is over.
So that's about thirty lines of computation, and a dozen additions, to compute A(2). Since the final result comes only from adding 1 over and over, the complexity of A(n) is greater than A(n) itself, which can't even be expressed with the usual operations! So no "simple" complexity can be given.
In practice, well... A(2) is easy to compute, I even did it here, with 27 recursive calls and 12 additions in all. A(3) is 61, and computing it takes 2432 recursive calls. A(4) is 2^(2^(2^65536))-3, and trying to compute it crashes your leek. So it grows very, very fast!
The Collatz sequence (also known as the Syracuse sequence) of a starting integer is a mathematical sequence defined by:
u(0) = a positive integer n u(i) = u(i-1)/2 if u(i-1) is even 3*u(i-1) + 1 otherwise
Notice that if the sequence ever takes the value 1, it will then go through the same values periodically: from 1 you go to 4, then to 2, then to 1, and it starts all over again.
So you can easily code a function that takes the starting integer as input and computes the associated Collatz sequence until it reaches 1:
function syracuse(n){ if(n === 1) {return "End of computation";} if(n%2 === 0) { return syracuse(n/2); } else { return syracuse(3*n + 1); } }
Will this function stop whatever the input? Well... I don't know. In fact, nobody knows: whether this function terminates is an open problem! It's therefore currently impossible to give the complexity of such a function. So be careful: just because a recursive function looks simple doesn't mean its complexity is easy to study...
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.
