Space complexity of this monotonic algorithm?

user_11295987 0
Viewed 111

I coded an algorithm to determine if an input array is a monotonic array (its elements from left to right are entirely increasing or entirely decreasing) or not.

I was wondering what the space complexity of this algorithm is. I am thinking it is O(n) because the count increases as the size of the array increases. Basically I am increasing the count every time the current element is <= or >= to the next element. So the largest value of count and count2 would basically be the size of the input array if the loop goes through every element.

Could someone please explain and correct me if I am wrong?

def monotonic(array):
    count = 0
    count2 = 0
    for i in range(len(array) - 1):
        if array[i] <= array[i + 1]:
            count += 1
        if array[i] >= array[i + 1]:
            count2 += 1
    if array == []: return True
    if count == len(array) - 1 or count2 == len(array) - 1:
        return True
    else:
        return False
space-complexity algorithm python
2 Answers

The time complexity is O(n).

The space complexity is O(1). The only storage used is for count and count2. There are no additional lists, nor are there recursive calls that would take up a variable amount of stack space.

user_685870

When counting size complexities, the usual assumption is that if something fits in memory, then its size fits into a constant number of bits, because the size of a computer's machine word is a constant defined by its architecture.

This is a pragmatic choice, and we make different assumptions when it's appropriate. The goal when making a statement of complexity is to say something useful. We all know that asymptotic analysis doesn't technically apply to real, bounded, machines, but it's a useful tool anyway.

user_54835260
Related