0

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?

Bazilion
  • 3
  • 2
  • 1
    Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Andrew Nov 07 '16 at 19:49
  • Who is telling you it isn't the right answer? Can you ask them? – Andrew Nov 07 '16 at 19:50

2 Answers2

1

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

Prune
  • 76,765
  • 14
  • 60
  • 81
0

It's 501*x since you also have to check x times the line if i == 0.

As the other answer says, usually we don't include the factor. But sometimes we do.

Rok Povsic
  • 4,626
  • 5
  • 37
  • 53