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.