[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [API]

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

- 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)?

- We might also ask more general questions about big-O notation.
- 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)?

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

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

[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [API]

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

This page may be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/98S/home/rebelsky/public_html/Courses/CS152/98S/Outlines/outline.19.html

Source text last modified Tue Jan 12 11:52:21 1999.

This page generated on Mon Jan 25 09:49:10 1999 by SiteWeaver. Validate this page.

Contact our webmaster at rebelsky@math.grin.edu