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
and
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.
2
Your first algorithm is O(n^2), as the outer loop executes n times, and on average the inner loop executes n/2 times; we discard the constant factor as we only care about asymptotic behavior.
Your second algorithm is I believe O(n log n): the outer loop again executes n times, so there must be a factor of n in the answer, and I believe the inner loop executes log n times on average.
Note that your suggested answer of O(log (n^2)) is not a valid answer in any case: log (n^2) = 2 log n, so O(log (n^2)) should be simplified to O(log n).
0