i'm here to clarify my understanding of the run times of these 2 algorithms
Alg1(n):
For i = 1 to n
j = 1
while i+j < n
j = j+1
Alg2(n):
For i = 1 to n
j = 1
while i*j < n
j = j+1
first algorithm is I believe is O(n) because the inner loop is bounded by n, and the while condition is incremented linearly as i is incremented by the outer for loop... otherwise I would say O(n^2)if i'm wrong
second algorithm I believe is O(log(n^2)), because as i increases, the amount of iterations will decrease in the while loop which is controlled by the outer for loop.
Insights and explanations will be grateful
Aucun commentaire:
Enregistrer un commentaire