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)
.
CodePudding user response:
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.
CodePudding user response:
To be precise, time complexity is O(n*m). Where n and m are the sizes of the arrays.