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.

• gnat: possible duplicate of What is O(...) and how do I calculate it?
• miracle173: you while loops iterate over j, starting with j=1 and incrementing it by 1 in each step. So why not use a for loop instead of the wihhile 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).