Récurrences diviser pour régner

Notations Soient (x_{n})_{n⩾1} et (y_{n})_{n⩾1} deux suites de réels ; on note x_{n} = Ω(y_{n}) lorsque y_{n} = O(x_{n}) ; on note x_{n} = Θ(y_{n}) lorsque l’on a simultanément x_{n} = O(y_{n}) et x_{n} = Ω(y_{n}). La partie entière du réel x est notée ⌊x⌋. On note ⌈x⌉ la ^{⟨⟨} partie entière supérieure^{⟩⟩} de x, id est : le plus petit relatif supérieur ou égal à x; on a donc ⌈x⌉ ∈ ℤ et ⌈x⌉ − 1 < x ⩽ ⌈x⌉. Soient : p ∈ ℕ^{∗}; (λ_{k})_{1⩽k⩽p} une famille de réels strictement positifs ; (α_{k})_{1⩽k⩽p} une famille de réels strictement supérieurs à 1 ; a un réel positif ou nul. On note S = ∑_{1⩽k⩽p} λ_{k}.

Dans toute la suite, on suppose S > 1.

On constate alors que l’application φ : t ⩾ 0 ↦ ∑_{1⩽k⩽p} \frac{λ_{k}}{α_{k}^{t}} est continue et strictement décroissante, donc

réalise une bijection de [1, +∞[ sur ]0, S]. Par conséquent, il existe un et un seul exposant γ > 0 tel que

∑_{1⩽k⩽p} \frac{λ_{k}}{α_{k}^{γ}} = 1.

Première partie Théorème 1 : si une suite (u_{n})_{n⩾1} de réels vérifie u_{n} ⩽ a + ∑_{1⩽k⩽p} λ_{k}u_{⌊n/α_{k}⌋} pour tout n ⩾ 2, alors u_{n} =

O(n^{γ}). Preuve

• Quitte à remplacer la suite de terme général u_{n} par celle de terme général u_{n} + \frac{a}{S − 1λ_{k}}, on peut supposer a = 0.

• Notons B = u_{1}, et établissons la majoration u_{n} ⩽ Bn^{γ} par récurrence sur n. Pour n = 1, la majoration résulte du choix de B. Supposons-la acquise jusqu’au rang n inclus ; pour tout k ∈ [[1, p]], on aura ⌊\frac{n + 1}{α_{k}}⌋ ⩽

\frac{n + 1}{α_{k}} < n + 1. D’où ⌊\frac{n + 1}{α_{k}}⌋ ⩽ n et par suite u_{⌊(n+1)/α_{k}⌋} ⩽ B(⌊\frac{n + 1}{α_{k}}⌋)^{γ}. Alors :

\begin{aligned}u_{n+1} & = ∑_{1⩽k⩽p} λ_{k}u_{⌊(n+1)/α_{k}⌋} ⩽ ∑_{1⩽k⩽p} λ_{k}B(⌊\frac{n + 1}{α_{k}}⌋)^{γ} \\ & ⩽ B ∑_{1⩽k⩽p} λ_{k}(\frac{n + 1}{α_{k}})^{γ} = B( ∑_{1⩽k⩽p} \frac{λ_{k}}{α_{k}^{γ}} )(n + 1)^{γ} = B(n + 1)^{γ} \end{aligned}

Ceci établit l’assertion au rang n + 1. Exemple 2 : recherche dans un 2d-arbre (Bentley, CACM 1975). On est amené à étudier une suite vérifiant la relation de récurrence C_{n} ⩽ 2 + 2C_{⌊n/4⌋}. Ici, p = 1, λ_{1} = 2 et α_{1} = 4 si bien que γ = 1/2 et C_{n} = O(\sqrt{n}). Théorème 2 : si une suite (u_{n})_{n⩾1} de réels vérifie u_{n} ⩾ a + ∑_{1⩽k⩽p} λ_{k}u_{⌊n/α_{k}⌋} pour tout n ⩾ 2, alors u_{n} =

Ω(n^{γ}). Preuve : notons A = 2^{−γ}u_{1} ; nous allons établir la minoration u_{n} ⩾ A(n + 1)^{γ} par récurrence sur n. On aura à plus forte raison u_{n} ⩾ An^{γ}. Pour n = 1, la minoration résulte du choix de A. Supposons-la acquise jusqu’au rang n inclus ; pour tout k ∈ [[1, p]], on aura comme précédemment ⌊\frac{n + 1}{α_{k}}⌋ ⩽ n, donc :

u_{⌊(n+1)/α_{k}⌋} ⩾ A(⌊\frac{n + 1}{α_{k}}⌋ + 1)^{γ} > A(\frac{n + 1}{α_{k}})^{γ}

ceci car ⌊x⌋ + 1 > x. On en déduit :

\begin{aligned}u_{n+1} & = ∑_{1⩽k⩽p} λ_{k}u_{⌊(n+1)/α_{k}⌋} ⩾ ∑_{1⩽k⩽p} λ_{k}A(⌊\frac{n + 1}{α_{k}}⌋ + 1)^{γ} \\ & ⩾ A ∑_{1⩽k⩽p} λ_{k}(\frac{n + 1}{α_{k}})^{γ} = A ∑_{1⩽k⩽p}(\frac{λ_{k}}{α_{k}^{γ}} )(n + 1)^{γ} = A(n + 1)^{γ} \end{aligned}

Ceci établit l’assertion au rang n + 1. Théorème 3 : la donnée de u_{1} > 0 et la relation de récurrence

u_{n} = a + ∑_{1⩽k⩽p} λ_{k}u_{⌊n/α_{k}⌋}

définissent une suite (u_{n})_{n⩾1} de réels positifs ; cette suite vérifie u_{n} = Θ(n^{γ}). Exemple : l’étude de la suite de Hamming (Dijkstra, A Discipline of Programming) amène à la récurrence T (n) = a + T (n/2) + T (n/3) + T (n/5) ; avec les notations de l’énoncé, p = 3, λ_{1} = λ_{2} = λ_{3} = 1, α_{1} = 2, α_{2} = 3, α_{3} = 5. Avec une calculatrice, on trouve γ ≈ 1.032812266 (merci à Michel Quercia), et T_{n} = Θ(n^{γ}).

Deuxième partie Nous allons nous intéresser maintenant aux suites (u_{n})_{n⩾1} vérifiant la relation de récurrence u_{n} = a +

∑_{1⩽k⩽p} λ_{k}u_{⌈n/α_{k}⌉}.

Commençons par régler un problème urgent : quels sont les termes dont il faut disposer pour ^{⟨⟨} amorcer^{⟩⟩} la récurrence ? On constate que, pour α > 1 :

⌈n/α⌉ < n ⇔ ⌈n/α⌉ ⩽ n − 1 ⇔ \frac{n}{α} ⩽ n − 1 ⇔ 1 ⩽ (1 − \frac{1}{α})n ⇔ n ⩾ \frac{1}{1 − \frac{1}{α}} = \frac{α}{α − 1} ⇔ n ⩾ ⌈\frac{α}{α − 1}⌉

Notons s(α) = ⌈\frac{α}{α − 1}⌉ et N = s(α_{1}) = max_{1⩽k⩽p} s(α_{k}). Pour être à même de calculer les termes de la suite, il est nécessaire et suffisant de connaître les termes d’indice n compris entre 1 (inclus) et N (exclus). Théorème 4 : si une suite (u_{n})_{n⩾1} de réels vérifie u_{n} ⩾ a + ∑_{1⩽k⩽p} λ_{k}u_{⌈n/α_{k}⌉} pour tout n ⩾ 2, alors u_{n} =

Ω(n^{γ}). Preuve : notons A = min_{1⩽n<N} \frac{u_{n}}{n^{γ}} et prouvons que u_{n} ⩽ An^{γ} pour tout n ⩾ 1. Pour 1 ⩽ n < N, la minoration résulte du choix de A. Supposons cette minoration acquise jusqu’au rang n ⩽ N − 1 inclus. Alors, en

utilisant ⌈\frac{n + 1}{α_{k}}⌉ ⩽ n et ⌈x⌉ ⩾ x:

\begin{aligned}u_{n+1} & = ∑_{1⩽k⩽p} λ_{k}u_{⌈(n+1)/α_{k}⌉} ⩾ ∑_{1⩽k⩽p} λ_{k}A(⌈\frac{n + 1}{α_{k}}⌉)^{γ} ⩾ A ∑_{1⩽k⩽p} λ_{k}(\frac{n + 1}{α_{k}})^{γ} \\ & = A( ∑_{1⩽k⩽p} \frac{λ_{k}}{α_{k}^{γ}} )(n + 1)^{γ} = A(n + 1)^{γ} \end{aligned}

Ceci établit l’assertion au rang n + 1. Théorème 5 : si une suite (u_{n})_{n⩾1} de réels vérifie u_{n} ⩽ a + ∑_{1⩽k⩽p} λ_{k}u_{⌈n/α_{k}⌉} pour tout n ⩾ 2, alors u_{n} =

O(n^{γ}). Preuve : pour établir cette majoration, il faut travailler un peu plus. Notons N′ = ⌊α_{p}(N − 1)⌋ + 1 ; pour k ∈ [[1, p]], on a :

n ⩾ N′ ⇒ n > α_{p}(N − 1) ⇒ n > α_{k}(N − 1) ⇒ \frac{n}{α_{k}} > N − 1 ⇒ ⌈\frac{n}{α_{k}} ⌉ ⩾ N

Soit C un réel strictement supérieur à \frac{α_{1}}{α_{1} − 1} ; on a certainement C > 1. Remarque : en fait, on peut prendre

C = \frac{α_{1}}{α_{1} − 1} sauf dans le cas où α_{1} = 2. Notons B = max_{N⩽n<N′} \frac{u_{n}}{(n − C)^{γ}} et prouvons que u_{n} ⩽ B(n−C)^{γ} pour tout n ⩾ N. Pour N ⩽ n < N′, cette majoration résulte du choix de B. Supposons la majoration acquise

pour tout indice compris entre N et N′ − 1 inclus. Alors, pour tout k ∈ [[1, p]], on a N ⩽ ⌈\frac{n + 1}{α_{k}}⌉ ⩽ n,

donc :

\begin{aligned}u_{n+1} & = ∑_{1⩽k⩽p} λ_{k}u_{⌈(n+1)/α_{k}⌉} ⩽ ∑_{1⩽k⩽p} λ_{k}B(⌈\frac{n + 1}{α_{k}}⌉ − C)^{γ} ⩽ B ∑_{1⩽k⩽p} λ_{k}(\frac{n + 1}{α_{k}} + 1 − C)^{γ} \\ & = B ∑_{1⩽k⩽p} \frac{λ_{k}}{α_{k}^{γ}} (n + 1 + (1 − C)α_{k}) \end{aligned}

Mais 1 − C < 1 − \frac{α_{1}}{α_{1} − 1} = −\frac{1}{α_{1} − 1} < 0 ; donc (1 − C)α_{k} ⩽ (1 − C)α_{1} ⩽ −\frac{α_{1}}{α_{1} − 1} < −C si bien que

n + 1 + (1 − C)α_{k} ⩽ n + 1 − C. On en déduit

u_{n+1} ⩽ B( ∑_{1⩽k⩽p} \frac{λ_{k}}{α_{k}^{γ}} )(n + 1 − C)^{γ} = B(n + 1 − C)^{γ}

ce qui établit la majoration au rang n + 1.

Théorème 5 : si une suite (u_{n})_{n⩾1} de réels vérifie u_{n}0a+ ∑_{1⩽k⩽p} λ_{k}u_{⌈n/α_{k}⌉} pour tout n ⩾ 2, alors u_{n} = Θ(n^{γ}).

Exemple : l’exercice 8.3 du monumental Introduction to Algorithms de Cormen, Leiserson et Rivest propose d’étudier une curieuse méthode de tri, baptisée Stooges Sort (référence cinématographique à des comiques américains des années trente, connus en France comme les Trois Nigauds). On est amené à étudier la suite (C_{n})_{n⩾2} définie par C_{2} = 1 et C_{n} = 3C_{⌈2n/3⌉} pour n ⩾ 3. Avec nos notations, p = 1, λ_{1} = 3 et α_{1} = 3/2 ; donc γ = \frac{ln 3}{ln 3/2}. Idée reprise dans l’exercice IV.10 du Cours et Exercices d’Informatique, qui attribue cette méthode aux Pieds Nickelés, plus connus du public français.Question apparue également au contrôle du 2 février 1997 du Magistère MMFAI de l’École Normale Supérieure de Paris, sous le nom de Strangesort.

[DpR] Composé le 24 mai 1998