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.

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

1 Answer 1

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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