0

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.

  • 1
    possible duplicate of What is O(...) and how do I calculate it? – gnat Jan 4 '15 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 Jan 4 '15 at 22:43
7

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.