CODEWITHSUNDEEP
pythonarraystime-complexityspace-complexity
srkdb
srkdb

Reputation: 815

O(1) space complexity for odd-even

I'm reordering the entries of an array so that the even ones (divisible by 2) appear first. The code snippet is as follows:

def even_odd(A):
    next_even , next_odd = 0, len(A) - 1
    while next_even < next_odd:
        if A[next_even] % 2 == 0:
           next_even += 1
        else:
           A[next_even], A[next_odd] = A[next_odd], A[next_even]
           next_odd -= 1

The time complexity is given as O(N) which I'm guessing is because I'm going through the whole array? But how's the space complexity O(1)?

Upvotes: 0

Views: 475

Answers (2)

Prune
Prune

Reputation: 77857

You use a fixed amount of space to reorder the list. That, by definition, is O(1). The fact that you're dealing with the length of A does not count against your function's space usage: A was already allocated by the problem definition. All you have added to that is two integers, next_even and next_odd: they are your O(1).

UPDATE per OP comment

The size of A does not "count against" your space complexity, as your algorithm uses the space already provided by the calling program. You haven't added any.

Sorry; I didn't realize you had an open question about the time complexity. Yes, your guess is correct: you go through the while loop N-1 times (N = len(A) ); each iteration takes no more than a constant amount of time. Therefore, the time complexity is bounded by N.

Upvotes: 2

Lior
Lior

Reputation: 84

I guess the meaning here that the "additional" memory required for the reordering is o(1), excluded the original array.

Upvotes: -1

Related Questions