Search code examples
python-3.xalgorithmspace-complexity

Will this algorithm be O(1) or O(n) space complexity

I have a homework question that is asking me to find a missing number in an array with an O(n) time complexity and O(1) space complexity program.

I feel like I have a pretty good grasp of what constitutes O(1) space complexity, however I am unsure of whether assigning a variable to be the largest value in the given array would make it O(n) space complexity. The code below is what I have written specifically

def findMissing(A):
    greatest = 0
    for i in range(len(A)):
        if A[i] > greatest:
            greatest = A[i]

I am thinking it would still be O(1) because the O(n) that I am trying to stay under is the full array containing the greatest value as well as all the other values, but at the same time my variable is still related to the input size, so I am unsure.

Solution

  • Since your code loops through the array once, it has O(n) time complexity. Storage only maintains 1 variable so it has O(1) space complexity. I'm assuming you left off the return statement for the sake of the question, otherwise, be sure you include that too.