self.array = nums: what is time complexity for assignment of lists in python?

Question

I was solving Dot Product of Two Sparse Vectors (Given two sparse vectors, compute their dot product.) and I got confused about time complexity.

For solution:

class SparseVector:
    def __init__(self, nums):
        self.array = nums

    def dotProduct(self, vec):
        result = 0
        for num1, num2 in zip(self.array, vec.array):
            result += num1 * num2
        return result

it says in answer that

Time complexity: O(n) for both constructing the sparse vector and calculating the dot product.

Why time complexity of __init__ is O(n)? I thought that self.array = nums is simple assignment like list_1 = list_2 and should has time complexity O(1).

seems that calculation is included in that time complexity, also probably by construction is meant instantiation and stuff — Matiiss
assignment is always constant time in Python. "Why does time complexity for constructing the sparse vector is O(n)? " What does that even mean? Please understand, questions must be self-contained. This site isn't for speculation about what some other, unspecified source is telling you. Your link requires a login. — juanpa.arrivillaga
@juanpa.arrivillaga I removed link. My question is simple: what time complexity of __init__? — illuminato

Mark Ransom Mark Ransom · Accepted Answer · 2022-07-28T18:09:51

You're right, the assignment is O(1). Assignment in Python never does any copying unless you explicitly make a copy, you just end up with two references to the same object. Doesn't matter how large the object is.

self.array = nums: what is time complexity for assignment of lists in python?

2 Answers