run time of nested while loop inside for loop

Question

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.

Answer 1

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).