Master theorem

Analysing complexity of recursive functions is not always easy, especially when the function does something fancy. Luckily, clever brains have provided a cookbook that makes determining the complexity of a recursive algorithm quite easy.

We may consider a recursive function as:
R(N) = A * R(\frac{N}{B}) + O(N^C)
Let me explain the symbols. R is a recursive function, that is called on the problem of size N. As it’s recursive, it calls itself A times, for a smaller problem of size N/B. In many recursive implementation, especially divide and conquer techniques, we got a “merge” step (please think about mergesort). The complexity of the merge step is expressed as the last term of the above formula.

Then we may determine three cases that will describe the complexity of the call.
1. A = B^C then O(R(N)) = N ^ C log N
2. A < B^C then O(R(N)) = N ^ C
3. A > B^C then O(R(N)) = N ^ {log _b{c}}

Do you remember mergesort? Mergesort has two recursive calls, that divide the problem into two pieces. When the recursion is done, then comes an extra “merge” step, that has O(N) complexity. If we plug this information into the formula we got: A = 2, B = 2, C = 1. What leads to 2 = 2 ^ 1. We take the first case, and obtain complexity of O(N) = N log N.

Find a permutation knowing its rank

Input: A number M, describing a rank of permutation of N elements
Output: Permutation with a given rank
Problem: We are given a rank and we need to find the proper permutation
Example: rank=1 p=123, rank = 2 p=132, rank = 3, p=213, etc.

In this article we have discussed how to find a rank of a permutation. Now let’s try to do the opposite thing: knowing the rank, find the proper permutation.

We will use the idea described in Skiena’s book, “The Algorithm Design Manual” (if you don’t have it yet, go and buy, as it’s a nice source of algorithmic problems and mr. Skiena seems to be a clever guy).

So we have a function Unrank(M, N), that according to the definition of the problem, tries to find what is the permutation at M position, in a permutation of N elements, having some order of generation.

Let me remind the Rank function from the article, that is given in the following way:

Rank(p) = (p_1 - 1) * (|p| - 1)! + Rank(p_2,...,p_{|p|})

How can we revert the permutation from the given rank number? The part (p_1 - 1) * (|p| - 1)! gives us an information how many permutations of size |p| appears, before we got  the value at p_1 at the first position. Then we proceed for the next number by a recursive call. In this case we have to find such a maximum number X for p_1, that there will be at max M permutations in front of him. So the following condition has to to be met:

(X - 1)*(N - 1) !<= M

Getting this number, we are updating ordering, as it was previously described in the rank algorithm and then we proceed for a problem with smaller size.

Let’s take an example to see if we correctly understand the problem. Let’s say we are looking for M = 3, N = 3.

Step 1.

Unrank(3, 3):
Ordering [1,2,3] => [1,2,3]
X = 3, then (3 - 1) * (3 - 1)!  = 4 > 3, condition not met
X = 2, then (2 - 1) * (3 - 1)! = 2 <= 3, condition met, so p1 = 2
Update the ordering removing 2, we [1,2,3] => [1,x, 3 - 1] = [1,2]

Step 2.

Unrank(1, 2):
Ordering [1,3] => [1,2]
X = 2, then (2 - 1) * (2 - 1)!  = 1 <= 2, condition ment, so p2 = 3
Update the ordering removing 2, we [1,2] => [1,x] = [1]

Step 3.

Unrank(0, 1):
Ordering [1] = [1]
As we are looking for 0 element for 1 element ordering it will be
exactly this element, so p3 = 1

So the given permutation is p = [2, 3, 1] and using rank algorithm we can really check that this answer is correct. The M parameter also changes with the recursion. If we figured out that the element with rank Y should be used, then in the next step M = max(M – Y, 0).

Best Regards

Joe Kidd

What is the rank of the given permutation?

Input: A permutation given as an array
Output: A number describing permutation rank
Problem: We are given a permutation and we need to find it’s rank: the position in the permutation sequence where it appears.
Example: 123, rank = 1, 132, rank = 2, 213, rank = 3, etc.

This is a very interesting problem, that leads to another one: recreating permutation on the base of rank number. But this one will be described later. This problem was met during algorithm challenge on Sphere Online Judge.

Obviously, one of the solution would be to generate all the permutations and check the position of the given one. But of course this solution is not satisfactory as the complexity would be O(n!).  We need to find a more clever idea.

There is a nice scientific article, if you want to understand the problem deeply. But here we will just keep it basic. Anyway here is the link to Science Direct article. Also Skiena describes a solution for this problem in his “The Algorithm Design Manual”, but for me it’s a little bit fuzzy and it took me a while to get what he means.

Basically the solution I suggest is the one from Skiena’s book, but I would like to explain it in a way that is easier to get, I hope. To make the description easier, let’s suppose the permutation is given as an array, i. e p = [3, 2, 1], describes a permutation of [1,2,3].

In Skiena’s book we are give an interesting recursive relation that looks like following:

Rank(p) = (p_1 - 1) * (|p| - 1)! + Rank(p_2,...,p_{|p|})

How should we interpret it? So we are given a permutation p, it’s rank is counted as a the value of the position number one minus 1, multiplied by the factorial of the size of permutation minus one. So far, so easy and nothing really difficult. But now, is the tricky part. What is exactly the recursive call parameter? It’s a “sub permutation” of p, without the first element and updated values according to a given order.

What do we understand by ordering? It’s the way we set up the order of given set of values. In example ordering of elements [1,2,3,4] is [1,2,3,4], but when we remove element 2 we got [1,3,4] and it’s ordering is [1,2,3] – it means in which place a given number appears in comparison to other elements from the set.

Let’s take an example. Let’s say we have a permutation p = [2, 1, 3] and we are trying to find it’s rank. So the recursive calls look like this:

Rank([2, 1, 3]) = (2 - 1) * 2! + Rank([1, 2])

Let’s stop for a while. How come, in the recursive call we get [1,2], as we already processed 2? Consider it, as after processing 2, it is removed from the ordering. So without 2, the value 3 is now the second element, but value 1 still remains 1. Keep in mind this is related strictly to the ordering you choose. So after this update, [1,3], becomes [1,2]. We process recursively and we get:

Rank([2, 1, 3]) = (2 - 1) * 2! + Rank([1, 2]) = 1 * 2 + 0*1 + Rank([1])

As you can see now we updated [2] to [1]. Finally we got:

Rank([2, 1, 3]) = (2 - 1) * 2! + Rank([1, 2]) = 1 * 2 + 0*1 + Rank([1]) = 1*2 + 0*1 + 0 = 2

You may try with some other permutations to see how it works. Or proceed to the article of unranking permutation.

Best Regards

Joe Kidd