# Outline of Class 19: Algorithm Analysis, Continued

Held: Wednesday, February 18, 1998

• Any questions on assignment 3?
• Note that many parts of this assignment can be found in the appropriate chapter of Bailey.
• Note also that there were some typos in the assignment which have now been fixed.
• The focus of today's class will be lab 8.

## Composing Functions

• Often, we can express the running time of an algorithm as a composition of other functions.
• For example, we might have a primary control structure which repeats its contents O(h(n)) times and within that control structure, we have a subalgorithm that takes O(g(n)) time.
• Similarly, we might break our algorithm up into two independent algorithms, one of which takes O(h(n)) time and one of which takes O(g(n)) time.
• We might also look at other relationships.
• Here are some questions we might ask ourselves about composition of functions.
• If f(n) is O(h(n)) and g(n) is O(k(n)), then what can we say about f(n) + g(n)?
• If f(n) is O(h(n)) and g(n) is O(k(n)), then what can we say about f(n) * g(n)?
• If f(n) is O(g(n)) and g(n) is O(h(n)) then what can we say about f(n) and h(n)?
• If f(n) is O(kg(n)) and k is a "constant", then what else can we say about f(n) and g(n)?
• If f(n) is O(g(n) + h(n)) and g(n) is O(h(n)), then what simpler thing can we say about f(n)?

## Related Notations

• There are a number of concepts like big-O notation.
• We say that a function f(n) is Omega(g(n)), which is read "Omega of g of n" if
• there exists a number n0
• there exists a number c > 0
• for all n > n0, abs(f(n)) >= abs(c*g(n))
• Omega provides a lower bound on the running time of an algorithm.
• We say that a function f(n) is theta(g(n)), which is read "theta of g of n" if
• there exists a number n0
• there exists a number c > 0
• there exists a number d > 0
• for all n > n0, c*g(n) <= abs(f(n)) <= abs(d*g(n))
• Theta notation gives a more precise running time, as it provides both a lower and upper bound on the running time.
• Some computer scientists look at even more abstract issues, such as the minimum running time for any algorithm that solves a particular type of problem.

## Lab

We'll spend much of today's class on an algorithm analysis lab.

On to Recursion
Back to Introduction to Algorithm Analysis
Outlines: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
Current position in syllabus

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.