Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
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 C++ program.

  ruledef1868

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_inline59303) that determines the bound.

  ruledef1881

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

for (int i = 0; i < n; ++i)
     tex2html_wrap60263;
Here tex2html_wrap_inline60305 is int i = 0, so its running time is constant ( tex2html_wrap_inline60307); tex2html_wrap_inline60309 is i < n, so its running time is constant ( tex2html_wrap_inline60311); and tex2html_wrap_inline60313 is ++i, so its running time is constant ( tex2html_wrap_inline60315). Also, the number of iterations is I(n)=n. According to Rule gif, the running time of this is tex2html_wrap_inline60319, which simplifies to tex2html_wrap_inline60321. Furthermore, if the loop body does anything at all, its running time must be tex2html_wrap_inline60323. Hence, the loop body will dominate the calculation of the maximum, and the running time of the loop is simply tex2html_wrap_inline60325.

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_inline60331.

  ruledef1904

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_inline60305, plus the larger of the running times of the then part, tex2html_wrap_inline60309, and the else part, tex2html_wrap_inline60313.


next up previous contents index

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