How is the time complexity of 2 nested while loops is o(N) in my function fixing?

Question

input = [10, 9, 7, 18, 13, 19, 4, 20, 21, 14]
Output : 10 9 18 7 20 19 4 13 14 21

def fixing(arr):
    oddIdx = 1
    evenIdx = 0
    while True:
        while evenIdx < len(arr) and arr[evenIdx] %2 ==0:
            evenIdx +=2
        while oddIdx < len(arr) and arr[oddIdx] % 2!=0:
            oddIdx+=2
        if evenIdx < len(arr) and oddIdx < len(arr):
            arr[evenIdx], arr[oddIdx] = arr[oddIdx], arr[evenIdx]
        else:
            break
    return arr

Is it because we are not ignoring the outer loop? If yes, why and if not, why not? Thank you!

Aviel Fedida · Accepted Answer · 2020-07-30 20:11:36Z

3

Lets break it down.

The condition for the while True depends on evenIdx < len(arr) and oddIdx < len(arr).

So the outer loop will not iterate more than O(N) where N=len(arr).

But what about the inner loops?

Lets consider the options here:

We only have 1 outer loop iteration where inner functions advance evenIdx and oddIdx to the point where we break. So overall O(N).
The outer loop iterate K times. But evenIdx and oddIdx do not reset. In iteration 1, evenIdx/oddIdx get to somewhere between 0 to N, iteration 2 they still continue to advance, same for iteration 3 up to iteration K. Eventually evenIdx/oddIdx advanced O(N) times. So again O(N).

There is a more strict analysis that can be done but it is still O(N).

edited Jul 30, 2020 at 20:11

answered Jul 30, 2020 at 19:51

Aviel Fedida

4,1129 gold badges59 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Barmar · Accepted Answer · 2020-07-30 19:52:32Z

1

It's because you don't reset evenIdx or oddIdx back to 0 each time through the outer loop. Each time the outer loop repeats, the inner loops start from where they left off the previous time.

So you don't perform multiple iterations over the list -- you break out of the outer loop as soon as both inner loops reach the end. And each inner loop only visits the even or odd elements once.

answered Jul 30, 2020 at 19:52

Barmar

789k57 gold badges555 silver badges669 bronze badges

2 Comments

superb rain Over a year ago

How do you know that the inner loops reach the end?

Barmar Over a year ago

If the inner loops haven't reached the end, the if statement swaps the even and odd elements. That means that the even/odd tests that failed on the previous iteration will succeed, so it will increment the indexes again. Eventually this process will reach the end.

Collectives™ on Stack Overflow

How is the time complexity of 2 nested while loops is o(N) in my function fixing?

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related