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.

possible duplicate of What is O(...) and how do I calculate it? — gnat
– gnat, Commented Jan 4, 2015 at 21:53
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? — miracle173
– miracle173, Commented Jan 4, 2015 at 22:43

Jules · Accepted Answer · 2015-01-04 21:26:00Z

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

Stack Exchange Network

run time of nested while loop inside for loop

1 Answer 1

Linked

Hot Network Questions

run time of nested while loop inside for loop

1 Answer 1

Linked

Related

Hot Network Questions