Bazilion Bazilion - 1 month ago 15
Python Question

Asymptotic complexity python

I have a task to find asymptotic complexity of this python code.

for i in range(x):
if i == 0:
for j in range(x):
for k in range(500):
print("A ")


By what I know it should be 500*x. Because the first cycle only goes once (i==0), second one goes x times and third one 500 times, so therefore it should be 500*x, shouldn´t it? However this isn´t the right answer. Could you help me out?

Answer

Asymptotic complexity describes the growth of execution time as the variable factors grow arbitrarily large. In short, constants added or multiplied don't count at all, since they don't change with the variable.

Yes, there are 500*x lines printed. You also have x-1 non-functional loop iterations. Your total time would be computed as something like

(x-1)[loop overhead] + x[loop overhead] + 500*x[loop overhead + print time]

However, the loop overhead, being a constant, is insignificant, and dropped out of the complexity expression. Likewise, the 500 is merely a scaling factor, and is also dropped from the expression.

The complexity is O(x).