I'm having some trouble figuring out the primitive count of operations for the following lines of code

def question1(n):
    n = n           # 1 ops
    i = 0           # 1 ops
    a = 0           # 1 ops
    while i < n:            # n ops
        j = 0               # n ops
        while j < n:        # n * n ops
            k = 0           # n * n ops
            while k < 60:                   # n * n * 60 ops
                a = i * j - i * 2   k       # n * n * 60 * 5 ops
                k  = 1                      # n * n * 60 * 2 ops
            j  = 1          # n * n ops
        i  = 1              # n ops

# total sum of prim operations = (n * n * 483)   (3 * n)   3

I'm not sure if

            while k < 60:                   # n * n * 60 ops
                a = i * j - i * 2   k       # n * n * 60 * 5 ops
                k  = 1                      # n * n * 60 * 2 ops

Is it really

n * n * 60?

or should it be

 n * n * n * 60

CodePudding user response：

"primitive operations" is an ambiguous concept. For instance, a while statement will at some point evaluate the condition as false (which you didn't count) and then make the execution jump to the statement after the loop. One could say those are two operations (evaluation jump).

Someone could say that k = 1 should count as 3 operations:

• load the value of k into a CPU register,
• add one to it
• store that register's value back in k.

But if Python were compiled into a machine language that has the INC instruction (like NASM), and we deal with fixed-size integers (like 32 bit), it is only one operation.

So this concept is fuzzy, and it is quite useless to sum them up. You should not identify "primitive operations", but identify chunks of code that have a constant time complexity.

Analysis in terms of constant time complexity

First we need to decide whether to think of integer arithmetic operations to be constant in time, or whether we should take into consideration that integers (certainly in Python) can have arbitrary size, and therefore these operations do not have a constant time complexity. See also "bit complexity". I will assume here that you want to regard arithmetic operations as having a constant time complexity.

Then we can identify this chunk of code has having a constant time complexity:

            k = 0
            while k < 60:
                a = i * j - i * 2   k
                k  = 1
            j  = 1

Note here that executing the inner block (that has a constant complexity) 60 times, still means the total has a constant time complexity, since 60 is a constant (independent from the input).

Also the initialisation of integer variables or their incrementing all represent constant time complexity.

There are two nested loops that each iterate