dimanche 4 janvier 2015

run time of nested while loop inside for loop


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