Questions sur l'algorithme médian randomisé?

Question

Dans le manuel de Mitzenmacher et Upfal ici, ils écrivent à la page 62, les suivants:

En répétant l'algorithme 3.1 jusqu'à ce qu'il réussit à trouver la médiane, nous pouvons obtenir un algorithme itératif qui ne manque jamais mais qui a un temps de fonctionnement aléatoire.

Notez que l'algorithme a un temps d'exécution linéaire. Maintenant, si nous répétons cet algorithme pour K fois, alors le temps d'exécution serait O (kN). Maintenant, comment ils disent que "en répétant l'algorithme jusqu'à ce qu'il réussit à trouver la médiane, nous pouvons obtenir un algorithme itératif"? Je ne comprends pas comment ils obtiennent un algorithme itératif. Afin d'obtenir un algorithme itératif, l'algorithme doit s'appeler et doit avoir un temps de fonctionnement logarithmique.

Une autre question: que signifient-ils par «il a un temps de fonctionnement aléatoire»?

À propos de l'algorithme itéré, veuillez regarder ici. Pour voir l'algorithme, regardez le livre à la page 59.