Domande sull'algoritmo mediano randomizzato?

Question

Nel libro di testo di Mitzenmacher e Upfal qui, scrivono a pagina 62, quanto segue:

Ripetendo l'algoritmo 3.1 fino a quando non riesce a trovare la mediana, possiamo ottenere un algoritmo iterativo che non fallisce mai ma ha un tempo di corsa casuale.

Si noti che l'algoritmo ha un tempo di esecuzione lineare. Ora, se ripetiamo questo algoritmo per K volte, il tempo di esecuzione sarebbe O (KN). Ora, come si dice che "ripetendo l'algoritmo fino a quando non riesce a trovare la mediana, possiamo ottenere un algoritmo iterativo"? Non capisco come ottengano un algoritmo iterativo. Per ottenere un algoritmo iterativo, l'algoritmo deve chiamarsi e deve avere un tempo di esecuzione logaritmico.

Un'altra domanda: cosa significano per "ha un tempo di esecuzione casuale"?

Informazioni sull'algoritmo iterato, per favore guarda qui. Per vedere l'algoritmo, guarda il libro a pagina 59.