Runtime analyzing

• Typically, the size of the input is the main consideration. We define two functions, Tavg(N) and TWORST(N), as the average and worst-case running time, respectively, used by an algorithm on input of size N. Clearly, Tavg(N) ≤ Tworst(N).
• Occasionally the best-case performance of an algorithm is analyzed. However, this is often of little interest, because it does not represent typical behavior. Average-case performance often reflects typical behavior, while worst-case performance represents a guarantee for performance on any possible input.
• Generally, the quantity required is the worst-case time, unless otherwise specified. One reason for this is that it provides a bound for all input, including particularly bad input, which an average-case analysis does not provide. The other reason is that average-case bounds are usually much more difficult to compute. In some instances, the definition of “average” can affect the result.
• The running time of a for loop is at most the running time of the statements inside the for loop (including tests) times the number of iterations.
• Analyze Nested Loops inside out. The total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the loops.
• The running time of an if/else statement is never more than the running time of the condition plus the larger of the running times of the statement in the if block plus the statement of the else block