Calculating the Running Time of a Program

To determine the total time required for a program, we add together the time required for each statement.

• The running time of a simple statement is O(1).

• The running time of an if statement is the larger of the running times of the two branches, plus the time required to evaluate the condition (which may be O(1) in some simple cases, but could be arbitrarily complex in other cases).

• The running time of a sequence of statements is the running time of the longest step.

• The running time of a loop is the time to execute one iteration times the number of iterations.