Ho il seguente programma:
Iterate x da 1 a N . Verifica se x è primo. Se lo è, aggiungilo a un elenco di numeri primi.
Il modo in cui controllo per vedere se è primo sta iterando attraverso l'attuale elenco di numeri primi, e vediamo se possono dividere equamente x .
Qual è l'analisi dell'ordine di questo programma? Non penso che sia O(n^2) , perché la crescente lista di numeri primi non aumenta certamente al tasso di n . Anche io non è O(nlog(n)) ,
Come eseguirò l'analisi degli ordini della funzione?