Running Time: Does Print Count as a Step?

Question

Suppose I have a function and I want to analyze the run-time of the exact number of steps:

def function(L):
    print ("Hello")
    i = 0                 # 1 step
    while i < len(L):     # 3 steps
        print (L[i] + 1)
        i += 2            # 2 steps
    print ("Goodbye")

I was wondering if print statements count as a step?

Yes, `print` would count as a step. I'm curious, though: why do you need the exact number of steps? Are you trying to analyze the function's complexity? Usually you want to do this by order of magnitude of the inputs. So you want to figure out, for example: if you double the size of L, by what multiple does the function's execution time increase? — pswaminathan, Jul 14 '13 at 20:11
In fact, `print` (and any other atomic statement) might actually be worth _many_ steps, depending on how you interpret step (e.g., CPU cycles, etc.). Also, not that your second `print` is at least three steps long: list access, addition, and print. To be accurate, it might be worth having a look at the generated byte code. — tobias_k, Jul 14 '13 at 20:20

score 6 · Answer 1 · edited May 23 '17 at 10:32

"Step" isn't a well-defined term in this context -- as pswaminathan points out, usually what we care about isn't a precise numerical value but the mathematical behavior in a broader sense: as the problem size gets bigger (in this case, if you increase the size of the input L) does the execution time stay the same? Grow linearly? Quadratically? Exponentially?

Explicitly counting steps can be a part of that analysis -- it can be a good way to get an intuitive handle on an algorithm. But we don't have a consistent way of determining what counts as a "step" and what doesn't. You could be looking at lines of code -- but in Python, for example, a list comprehension can express a long, complicated loop in a single line. Or you could be counting CPU instructions, but in a higher-level language full of abstractions that's hopelessly difficult. So you pick a heuristic -- in straightforward code like your example, "every execution of a single line of code is a step" is a decent rule. And in that case, you'd certainly count the print statements. If you wanted to get in a little deeper, you could look at the bytecode as tobias_k suggests, to get a sense for what the instructions look like behind Python's syntax.

But there's no single agreed-upon rule. You mention it's for homework; in that case, only your instructor knows what definition they want you to use. That said, the simple answer to your question is most likely "yes, the print statements count."

score 4 · Answer 2 · edited May 23 '17 at 11:56

If your task is to count the exact number of steps, then yes, print would count as a step. But note also that your second print is at least three steps long: list access, addition, and print.

In fact, print (and other 'atomic' statements) might actually be worth many "steps", depending on how you interpret step, e.g., CPU cycles, etc. This may be overkill for your assignment, but to be accurate, it might be worth having a look at the generated byte code. Try this:

import dis
print dis.dis(function)

This will give you the full list of more-or-less atomic steps in your function, e.g., loading a function, passing arguments to that function, popping elements from the stack, etc. According to this, even your first print is worth three steps (in Python 2.6):

2           0 LOAD_CONST               1 ('Hello')
            3 PRINT_ITEM          
            4 PRINT_NEWLINE

How to interpret this: The first number (2) is the line number (i.e., all the following instructions are for that line alone); the central numbers (0) are jump labels (used by, e.g., if-statements and loops), followed by the actual instructions (LOAD_CONST); the right column holds the arguments for those instructions ('Hello'). For more details, see this answer.

Running Time: Does Print Count as a Step?

2 Answers2