CODEWITHSUNDEEP
pythontime-complexity
Alexander Ameye
Alexander Ameye

Reputation: 185

Where did I go wrong in this time complexity calculation?

I have this function in Python:

digit_sum = 0
while number > 0:
   digit_sum += (number % 10)
   number = number // 10

For determining the time complexity, I applied the following logic:

Line 1: 1 basic operation (assignment), gets executed 1 time so gets a value of 1

Line 2: 2 basic operations (reading the variable 'number' and comparing against zero), gets executed n+1 times so gets a value of 2*(n+1)

Line 3: 4 basic operations (reading the variable 'number', %10, computing the sum, and assignment), gets executed n times so gets a value of 4*n

Line 4: 3 basic operations (reading the variable 'number', //10 and assignment), gets executed n times so gets a value of 3*n

This brings me to a total of 1 + 2n+2 + 4n + 3n = 9n+3

But my textbook has a solution of 8n+3. Where did I go wrong in my logic?

Thanks,

Alex

Upvotes: 3

Views: 52

Answers (1)

spectras
spectras

Reputation: 13542

When talking about complexity all you really care about is asymptotic complexity. Here, O(n). The 8 or 9 or 42 doesn't really matter, especially as there is no way for you to know.

Thus counting "operations" is pointless. It exposes the architectural details of the underlying processor (be it an actual hw proc or an interpreter). The only way to actually get the "real" count of operations would be to have a look at a specific implementation (for instance, say CPython 3.6.0) and see the bytecode it generates from your program.

Here is what my CPython 2.7.12 does:

>>> def test(number):
...     digit_sum = 0
...     while number > 0:
...         digit_sum += (number % 10)
...         number = number // 10
...
>>> import dis
>>> dis.dis(test)
  2           0 LOAD_CONST               1 (0)
              3 STORE_FAST               1 (digit_sum)

  3           6 SETUP_LOOP              40 (to 49)
        >>    9 LOAD_FAST                0 (number)
             12 LOAD_CONST               1 (0)
             15 COMPARE_OP               4 (>)
             18 POP_JUMP_IF_FALSE       48

  4          21 LOAD_FAST                1 (digit_sum)
             24 LOAD_FAST                0 (number)
             27 LOAD_CONST               2 (10)
             30 BINARY_MODULO
             31 INPLACE_ADD
             32 STORE_FAST               1 (digit_sum)

  5          35 LOAD_FAST                0 (number)
             38 LOAD_CONST               2 (10)
             41 BINARY_FLOOR_DIVIDE
             42 STORE_FAST               0 (number)
             45 JUMP_ABSOLUTE            9
        >>   48 POP_BLOCK
        >>   49 LOAD_CONST               0 (None)
             52 RETURN_VALUE

I let you draw your own conclusions as to what you want to actually count as a basic operation. Python interpreter interprets bytecodes one after the other, so arguably you have 15 "basic operations" inside your loop. That's the closest you can get to a meaningful number. Still, every operation in there has different runtimes so that 15 carries no valuable information.

Also, keep in mind this is specific to CPython 2.7.12. It's very likely another version will generate something else, taking advantage of new bytecodes that might make it possible to express some operations in a simpler way.

Upvotes: 2

Related Questions