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.