CODEWITHSUNDEEP
pythontime-complexitybig-o
JDF91
JDF91

Reputation: 35

Calculating time complexity of a python algorithm

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

Upvotes: 0

Views: 141

Answers (1)

Ivan Kwong
Ivan Kwong

Reputation: 381

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)

Upvotes: 1

Related Questions