En réalité, plusieurs langages purs modernes fournissent des tableaux qu'on peut modifier en O(1). Ainsi on peut traduire n'importe quel algorithme impératif en une version pur qui passe un tableau à chaque opération, et le nombre d'opérations (donc l'expression O()) reste le même.
(Cela dit, parfois on préfère écrire la version Θ(n log n).)
[^] # Re: Beurk, un langage impératif
Posté par Peter Moulder . En réponse à la dépêche OCaml 3.10.0 est sorti. Évalué à 1.
(Cela dit, parfois on préfère écrire la version Θ(n log n).)