Introduction to Algorithms

211591

CS 5002: Discrete Structures Fall 2018

Lecture 9: November 8, 2018

1

Instructors: Adrienne Slaughter, Tamara BonaciDisclaimer:These notes have not been subjected to the usual scrutiny reserved for formal publications.

They may be distributed outside this class only with the permission of the Instructor.

Introduction to Algorithms

Readings for this week:

Rosen, Chapter 2.1, 2.2, 2.5, 2.6

Sets, Set Operations, Cardinality of Sets, Matrices9.1 Overview

Objective: Introduce algorithms.

1.

Review logarithms

2.

Asymptotic analysis

3.

Dene Algorithm

4.

Ho wto express or describ ean algorithm

5.

Run time, space (Resource usage )

6.

Determining Correctness

7.

In troducerepresen tativeproblems

1. fo o

9.2 Asymptotic Analysis

The goal with asymptotic analysis is to try to nd a bound, or an asymptote, of a function. This allows

us to come up with an \ordering" of functions, such that one function is denitely bigger than another,

in order to compare two functions. We do this by considering the value of the functions asngoes to innity, so for very large values ofn, as opposed to small values ofnthat may be easy to calculate. Once we have this ordering, we can introduce some terminology to describe the relationship of two functions. 9-1

9-2Lecture 9: November 8, 201823456781248163264128256512102420484096n!n

n2 nn

2nlog(n)log(n)n

pn

1Growth of Functions

From this chart, we see:

1lognpnnnlog(n)n22nn!nn(9.1)

ComplexityTerminology

(1)Constant (logn)Logarithmic (n)Linear (nlogn)Linearithmic nbPolynomial (bn) (whereb >1)Exponential (n!)Factorial

9.2.1 Big-O: Upper BoundDenition 9.1 (Big-O: Upper Bound)f(n) =O(g(n))means there exists some constantcsuch

thatf(n)cg(n), for large enoughn(that is, asn! 1).

We sayf(n) =O(g(n))

Example:I claim 3n2100n+ 6 =O(n2). I can prove this using the denition of big-O:

Lecture 9: November 8, 20189-3

f(n) = 3n2100n+ 6 (9.2) g(n) =n2(9.3) )3n2100n+ 6cn2for somec(9.4)

Ifc= 3 : 3n2100n+ 63n2(9.5)

To prove using Big-O:

Determinef(n) andg(n)

Write the equation based on the denition

Choose acsuch that the equation is true.

{If you can nd ad, thenf(n) =O(g(n)). If not, thenf(n)6=O(g(n)).

These statements are all true:

3n2100n+ 6 =O(n2) (9.6)

3n2100n+ 6 =O(n3) (9.7)

3n2100n+ 66=O(n) (9.8)

Proving

9.7 f(n) = 3n2100n+ 6 (9.9) g(n) =n3(9.10) )3n2100n+ 6 =cn3(for somec) (9.11)

Ifc= 1 : 3n2100n+ 6n3(whenn >3) (9.12)

We also know this to be true because order istransitive: iff(n) =O(g(n)), andg(n) =O(h(n)), then f(n) =O(h(n)). Sincen2=O(n3), then anyf(n) =O(n2) is alsoO(n3).

Proving

9.8 f(n) = 3n2100n+ 6 (9.13) g(n) =n(9.14)

For anyc:cn <3n2(whenn > c) (9.15)

9.2.2 Big-Omega: Lower BoundDenition 9.2 (Big-Omega: Lower Bound)f(n) =

(g(n))means there exists some constantc such thatf(n)cg(n), for large enoughn(that is, asn! 1).

We sayf(n) =

(g(n))or \fofnis Big Omega ofgofn"

9-4Lecture 9: November 8, 2018

Example:I claim 3n2100n+ 6 =

(n2). I can prove this using the denition of big-Omega: f(n) = 3n2100n+ 6 (9.16) g(n) =n2(9.17) )3n2100n+ 6cn2for somec(9.18)

Ifc= 2 : 3n2100n+ 62n2(9.19)

We show Big-Omega the same way we show Big-O.

These statements are all true:

3n2100n+ 6 =

(n2) (9.20)

3n2100n+ 66=

(n3) (9.21)

3n2100n+ 6 =

(n) (9.22)

Proving

9.21

CS 5002: Discrete Structures Fall 2018

Lecture 9: November 8, 2018

1

Instructors: Adrienne Slaughter, Tamara BonaciDisclaimer:These notes have not been subjected to the usual scrutiny reserved for formal publications.

They may be distributed outside this class only with the permission of the Instructor.

Introduction to Algorithms

Readings for this week:

Rosen, Chapter 2.1, 2.2, 2.5, 2.6

Sets, Set Operations, Cardinality of Sets, Matrices9.1 Overview

Objective: Introduce algorithms.

1.

Review logarithms

2.

Asymptotic analysis

3.

Dene Algorithm

4.

Ho wto express or describ ean algorithm

5.

Run time, space (Resource usage )

6.

Determining Correctness

7.

In troducerepresen tativeproblems

1. fo o

9.2 Asymptotic Analysis

The goal with asymptotic analysis is to try to nd a bound, or an asymptote, of a function. This allows

us to come up with an \ordering" of functions, such that one function is denitely bigger than another,

in order to compare two functions. We do this by considering the value of the functions asngoes to innity, so for very large values ofn, as opposed to small values ofnthat may be easy to calculate. Once we have this ordering, we can introduce some terminology to describe the relationship of two functions. 9-1

9-2Lecture 9: November 8, 201823456781248163264128256512102420484096n!n

n2 nn

2nlog(n)log(n)n

pn

1Growth of Functions

From this chart, we see:

1lognpnnnlog(n)n22nn!nn(9.1)

ComplexityTerminology

(1)Constant (logn)Logarithmic (n)Linear (nlogn)Linearithmic nbPolynomial (bn) (whereb >1)Exponential (n!)Factorial

9.2.1 Big-O: Upper BoundDenition 9.1 (Big-O: Upper Bound)f(n) =O(g(n))means there exists some constantcsuch

thatf(n)cg(n), for large enoughn(that is, asn! 1).

We sayf(n) =O(g(n))

Example:I claim 3n2100n+ 6 =O(n2). I can prove this using the denition of big-O:

Lecture 9: November 8, 20189-3

f(n) = 3n2100n+ 6 (9.2) g(n) =n2(9.3) )3n2100n+ 6cn2for somec(9.4)

Ifc= 3 : 3n2100n+ 63n2(9.5)

To prove using Big-O:

Determinef(n) andg(n)

Write the equation based on the denition

Choose acsuch that the equation is true.

{If you can nd ad, thenf(n) =O(g(n)). If not, thenf(n)6=O(g(n)).

These statements are all true:

3n2100n+ 6 =O(n2) (9.6)

3n2100n+ 6 =O(n3) (9.7)

3n2100n+ 66=O(n) (9.8)

Proving

9.7 f(n) = 3n2100n+ 6 (9.9) g(n) =n3(9.10) )3n2100n+ 6 =cn3(for somec) (9.11)

Ifc= 1 : 3n2100n+ 6n3(whenn >3) (9.12)

We also know this to be true because order istransitive: iff(n) =O(g(n)), andg(n) =O(h(n)), then f(n) =O(h(n)). Sincen2=O(n3), then anyf(n) =O(n2) is alsoO(n3).

Proving

9.8 f(n) = 3n2100n+ 6 (9.13) g(n) =n(9.14)

For anyc:cn <3n2(whenn > c) (9.15)

9.2.2 Big-Omega: Lower BoundDenition 9.2 (Big-Omega: Lower Bound)f(n) =

(g(n))means there exists some constantc such thatf(n)cg(n), for large enoughn(that is, asn! 1).

We sayf(n) =

(g(n))or \fofnis Big Omega ofgofn"

9-4Lecture 9: November 8, 2018

Example:I claim 3n2100n+ 6 =

(n2). I can prove this using the denition of big-Omega: f(n) = 3n2100n+ 6 (9.16) g(n) =n2(9.17) )3n2100n+ 6cn2for somec(9.18)

Ifc= 2 : 3n2100n+ 62n2(9.19)

We show Big-Omega the same way we show Big-O.

These statements are all true:

3n2100n+ 6 =

(n2) (9.20)

3n2100n+ 66=

(n3) (9.21)

3n2100n+ 6 =

(n) (9.22)

Proving

9.21