What is the complexity of this pseudo-code

user_11636760 0
Viewed 2453

I found this excersise in the exam and I ecountered difficulty to solve the problem.

I can suppuse for sure the algorithm will take at least O(n) due the for, but I don't know how to approach the while. I know that in this case i have to evaluate the worst if-else branch and for sure it is the second one.

for i=1...n do
    j=n
    while i<j do
        if j mod 2 = 0 then j=j-1
        else j=i

intuitively i think the total cost is: O(nlogn)=O(n)*O(logn)

pseudocode complexity-theory time-complexity algorithm
2 Answers

In short: the while loop will each time run at most two iterations. This makes the algorithm O(n).

The while loop will iterate at most two times. Indeed let us take a look at the while loop:

while i < j do
    if j mod 2 = 0 then
        j=j-1
    else
        j=i

It is clear that we will only execute the while loop if i < j. Furthermore if j mod 2 == 1 (so j is odd), then it will set j = i, and thus the while loop will no longer run.

If on the other hand j mod 2 == 0 (so j is even), then we decrement j. There are now two things that could happen, either i == j, in which case we do not perform an extra iteration. If we however perform an extra iteration, the if condition will fail, since decrementing an even number results in an odd number. Since we each time set j = n, it also means that the number of steps that the while loop performs is determined by n itself.

This thus means that regardless what the values for i and j are, the body of the while loop will be performed at most two times.

Since we perform the while loop extactly n times, it thus means that the algorithm is still O(n). We here make the assumption that we can check the parity of a number and decrement a number in constant time.

user_675790

Does mod refer to Modulo? In that case, the while loop will evaluate at most twice; once to decrement j, but then j mod 2 will be 1, and after setting j=i your i<j will be false. The complexity difference here oscillates rather than increases with input, and is thus O(1) for this branch.

user_23911690
Related