I'm here to clarify my understanding of the run times of these 2 algorithms:
Algorithm1(n): For i = 1 to n j = 1 while i+j < n j = j+1
Algorithm2(n): For i = 1 to n j = 1 while i*j < n j = j+1
The first algorithm 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.
The 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.