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.

  ruledef1958

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

  ruledef1971

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_wrap59491;
Here tex2html_wrap_inline59533 is int i = 0, so its running time is constant ( tex2html_wrap_inline59535); tex2html_wrap_inline59537 is i < n, so its running time is constant ( tex2html_wrap_inline59539); and tex2html_wrap_inline59541 is ++i, so its running time is constant ( tex2html_wrap_inline59543). Also, the number of iterations is I(n)=n. According to Rule gif, the running time of this is tex2html_wrap_inline59547, which simplifies to tex2html_wrap_inline59549. Furthermore, if the loop body does anything at all, its running time must be tex2html_wrap_inline59551. Hence, the loop body will dominate the calculation of the maximum, and the running time of the loop is simply tex2html_wrap_inline59553.

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

  ruledef1994

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_inline59533, plus the larger of the running times of the then part, tex2html_wrap_inline59537, and the else part, tex2html_wrap_inline59541.


next up previous contents index

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