Calculating time complexity of a python algorithm

Question

I am trying to calculate the time complexity of this algorithm and failing horribly I think. Can anyone tell if I'm on the right track here? any help would be greatly appreciated. (:

data = [["Jacob", "91"], ["John", "81"], ["James", "71"], ["Joe", "61"]] size n


name = "Joe"
not_found = True
index = 0
marks = 0


for i in range(len(data)): # n
    if name == data[i][0]: # n(3)
        marks = data[i][1] # n(3)(3)
print(marks) #1

#T(n) = n + 3n +9n^2 + 1
#T(n) = 9n^2 +4n + 1
#O(n) = 9n^2

It is O(n). You are iterating n times and every time you do a O(1) operation (if statement), and only once you get to do another O(1) operation (marks = ...), so O(n*1+1) -> O(n) — Rob
– Rob, Commented Mar 26, 2022 at 14:12

Ivan Kwong · Accepted Answer · 2022-03-26 14:31:55Z

1

I think a better way to approach this problem is to think how many times you run the same command.

for i in range(len(data)): 
    if name == data[i][0]:
        marks = data[i][1]  # <- this command only runs n times

so this is O(n), since you run this command n times

marks = 0
for _ in range(len(data)): 
    for _ in range(len(data)): 
        marks += 1  #  <- this command only runs n^2 times

so this is O(n^2)

answered Mar 26, 2022 at 14:31

Ivan Kwong

3811 silver badge6 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Calculating time complexity of a python algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related