Where did I go wrong with this time complexity calculation?
I have this function in Python:
digit_sum = 0
while number > 0:
digit_sum += (number % 10)
number = number // 10
To determine the time complexity, I applied the following logic:
Line 1: 1 basic operation (assignment), done 1 time, so gets the value 1
Line 2: 2 basic operations (reading the variable "number" and comparing with zero), performed n + 1 times, so it gets the value 2 * (n + 1)
Line 3: 4 basic operations (reading the variable "number",% 10, calculating the sum and assignment), it is executed n times, so it gets the value 4 * n
Line 4: The 3 main operations (reading the variable "number", // 10 and assignment), is performed n times, so it gets the value 3 * n
This brings me to the sum 1 + 2n + 2 + 4n + 3n = 9n + 3
But my tutorial has an 8n + 3 solution . Where did I go wrong in my logic?
Thank,
Alex
source to share
When you talk about complexity that you really care about is asymptotic complexity . Here O (n). 8 or 9 or 42 doesn't really matter, especially since you can't know.
Thus, counting "operations" is meaningless. It provides the architectural details of the underlying processor (be it an actual hw proc or an interpreter). The only way to get a "real" number of operations is to look at a specific implementation (eg CPython 3.6.0) and see how the bytecode generates it from your program.
This 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'll let you draw your own conclusions about what you want to actually count as the main operation. The Python interpreter interprets the bytecodes one by one, so perhaps you have 15 "basic operations" inside your loop. What's the closest you can get to a meaningful number. However, each operation there has different run times, so 15 does not carry any valuable information.
Also, keep in mind that this is specific to CPython 2.7.12. Probably another version will generate something else using new bytecodes that could simplify some operations.
source to share