Bazilion - 1 year ago 107

Python Question

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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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)**.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**