Barrapunto

Puedo estar equivocado, sólo he leido literatura de divulgación sobre esto. Pero creo que ocurre con la mayoría de los algoritmos probabilísticos para determinar si un número n es primo es que, no se conoce a priori un tiempo t tal que el tiempo en decidir que n es primo con una probabilidad p es menor que ese tiempo t. Lo que no es exactamente que no terminen en tiempo finito, reconozco. ¿Estoy equivocado?