Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Rules For Big Oh Analysis of Running Time

In this section we present some simple rules for determining a big-oh upper bound on the running time of the basic compound statements  in a Java program.

  ruledef1952

Rule gif follows directly from Theorem gif. The total running time of a sequence of statements is equal to the sum of the running times of the individual statements. By Theorem gif, when computing the sum of a series of functions it is the largest one (the tex2html_wrap_inline58246) that determines the bound.

  ruledef1965

Rule gif appears somewhat complicated due to the semantics of the Java for statement. However, it follows directly from Theorem gif. Consider the following simple counted do loop .

for (int i = 0; i < n; ++i)
     tex2html_wrap59210;
Here tex2html_wrap_inline59252 is int i = 0, so its running time is constant ( tex2html_wrap_inline59254); tex2html_wrap_inline59256 is i < n, so its running time is constant ( tex2html_wrap_inline59258); and tex2html_wrap_inline59260 is ++i, so its running time is constant ( tex2html_wrap_inline59262). Also, the number of iterations is I(n)=n. According to Rule gif, the running time of this is tex2html_wrap_inline59266, which simplifies to tex2html_wrap_inline59268. Furthermore, if the loop body does anything at all, its running time must be tex2html_wrap_inline59270. Hence, the loop body will dominate the calculation of the maximum, and the running time of the loop is simply tex2html_wrap_inline59272.

If we don't know the exact number of iterations executed, I(n), we can still use Rule gif provided we have an upper bound, I(n)=O(f(n)), on the number of iterations executed. In this case, the running time is tex2html_wrap_inline59278.

  ruledef1988

Rule gif follows directly from the observation that the total running time for an if-then-else statement will never exceed the sum of the running time of the conditional test, tex2html_wrap_inline59252, plus the larger of the running times of the then part, tex2html_wrap_inline59256, and the else part, tex2html_wrap_inline59260.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.