Sono qui per chiarire la mia comprensione dei tempi di esecuzione di questi 2 algoritmi:
Algorithm1(n):
For i = 1 to n
j = 1
while i+j < n
j = j+1
e
Algorithm2(n):
For i = 1 to n
j = 1
while i*j < n
j = j+1
Il primo algoritmo credo sia O(n) perché il ciclo interno è limitato da n e la condizione while viene incrementata linearmente quando i viene incrementata dal ciclo for esterno. Altrimenti, direi O(n^2) se sbaglio.
Il secondo algoritmo credo sia O(log(n^2)) perché, con il crescere di i , la quantità di iterazioni diminuirà nel ciclo while che è controllato dal ciclo for esterno.