Introduction to Algorithms

215169

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 f(n) = 3n2100n+ 6 (9.23) g(n) =n3(9.24) )3n2100n+ 6cn3(for somec) (9.25)

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

Proving

9.22 f(n) = 3n2100n+ 6 (9.27) g(n) =n(9.28)

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

9.2.3 Big-Theta: \Tight" BoundDenition 9.3 (Big-Theta: \Tight" Bound)f(n) = (g(n))means there exists some constantsc1

andc2such thatf(n)c1g(n)andf(n)c2g(n).

We sayf(n) = (g(n))or \fofnis Big-Theta ofgofn".

Denition 9.4 (Theta and \order of")Whenf(x) = (g(x)), it is the same as sayingf(x)is the order ofg(x), or thatf(x)andg(x)are the same order.

3n2100n+ 6 = (n2)Both Oand

apply

Lecture 9: November 8, 20189-5

3n2100n+ 66= (n3)Only Oapplies

3n2100n+ 66= (n)Only

app lies Interesting AsideDonald Knuth popularized the use of Big-O notation. It was originally inspired by the use of \ell" numbers, written asL(5), which indicates a number that we don't know the exact

value of, but is less than 5. That allows us to reason about the value without knowing the exact value:

we knowL(5)<100, for example. Theorem 9.5Iff(x) =anxn+an1xn1++a1x+a0, thenf(x) =O(n) a)f(x) = 17x+ 11 b)f(x) =x2+ 1000 c)f(x) =xlogxd)f(x) =x4=2 e)f(x) = 2xf)f(x) =bxc dxe

9.2.4 Logs, Powers, Exponents

We've seenf(n) =O(nd). Ifd > c >1, thennc=O(nc).ncisOnd;butndis notO(nc). log bnisO(n) wheneverb >1. Wheneverb >1, c and d are positive: (log bn)cisOnd;butndis not (O(logbn)c) (9.30)

This tells us that every positive power of the logarithm of n to the base b, where b > 1, is big-O of every

positive power of n, but the reverse relationship never holds. In Example 7, we also showed that n is

O(2n). More generally, whenever d is positive and b > 1, we have n disO(bn);butbnis notOnd(9.31)

This tells us that every power of n is big-O of every exponential function of n with a base that is greater

than one, but the reverse relationship never holds. Furthermore, we have when c > b > 1, b nisO(cn) butcnis notO(bn) (9.32)

This tells us that if we have two exponential functions with dierent bases greater than one, one of these

functions is big-O of the other if and only if its base is smaller or equal.

9.2.5 Adding Functions

There are a set of rules that govern combining functions together.

O(f(n)) +O(g(n))!O(max(f(n);g(n))) (9.33)

(f(n)) + (g(n))! (max(f(n);g(n))) (9.34) (f(n)) + (g(n))!(max(f(n);g(n)) (9.35) These statements express the notion that the largest term of the statement is the dominant one. For example,n3+ 2n2+ 3 =O(n3).

Example:Prove thatn2=O(2n).

9-6Lecture 9: November 8, 2018Example:Prove that iff1(n) =O(g1(n)) andf2(n) =O(g2(n)), thenf1(n)+f(n) =O(g1(n)+g2(n)).Example:

f(n) =n+ logn(9.36) g(n) =p(n) (9.37)

Isf(n) =O(g(n)),g(n) =O(f(n)), or both?Example:Iff(n) =n+ logn+pn, nd a simple functiongsuch thatf(n) = (g(n)).

Lecture 9: November 8, 20189-7Summary

f(n) =O(g(n)) meanscg(n) is an upper bound onf(n). Thus there exists some constantcsuch thatf(n) is alwayscg(n), for large enoughn(i.e.,nn0for some constantn0). f(n) = (g(n)) meanscg(n) is a lower bound onf(n). Thus there exists some constantcsuch

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 f(n) = 3n2100n+ 6 (9.23) g(n) =n3(9.24) )3n2100n+ 6cn3(for somec) (9.25)

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

Proving

9.22 f(n) = 3n2100n+ 6 (9.27) g(n) =n(9.28)

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

9.2.3 Big-Theta: \Tight" BoundDenition 9.3 (Big-Theta: \Tight" Bound)f(n) = (g(n))means there exists some constantsc1

andc2such thatf(n)c1g(n)andf(n)c2g(n).

We sayf(n) = (g(n))or \fofnis Big-Theta ofgofn".

Denition 9.4 (Theta and \order of")Whenf(x) = (g(x)), it is the same as sayingf(x)is the order ofg(x), or thatf(x)andg(x)are the same order.

3n2100n+ 6 = (n2)Both Oand

apply

Lecture 9: November 8, 20189-5

3n2100n+ 66= (n3)Only Oapplies

3n2100n+ 66= (n)Only

app lies Interesting AsideDonald Knuth popularized the use of Big-O notation. It was originally inspired by the use of \ell" numbers, written asL(5), which indicates a number that we don't know the exact

value of, but is less than 5. That allows us to reason about the value without knowing the exact value:

we knowL(5)<100, for example. Theorem 9.5Iff(x) =anxn+an1xn1++a1x+a0, thenf(x) =O(n) a)f(x) = 17x+ 11 b)f(x) =x2+ 1000 c)f(x) =xlogxd)f(x) =x4=2 e)f(x) = 2xf)f(x) =bxc dxe

9.2.4 Logs, Powers, Exponents

We've seenf(n) =O(nd). Ifd > c >1, thennc=O(nc).ncisOnd;butndis notO(nc). log bnisO(n) wheneverb >1. Wheneverb >1, c and d are positive: (log bn)cisOnd;butndis not (O(logbn)c) (9.30)

This tells us that every positive power of the logarithm of n to the base b, where b > 1, is big-O of every

positive power of n, but the reverse relationship never holds. In Example 7, we also showed that n is

O(2n). More generally, whenever d is positive and b > 1, we have n disO(bn);butbnis notOnd(9.31)

This tells us that every power of n is big-O of every exponential function of n with a base that is greater

than one, but the reverse relationship never holds. Furthermore, we have when c > b > 1, b nisO(cn) butcnis notO(bn) (9.32)

This tells us that if we have two exponential functions with dierent bases greater than one, one of these

functions is big-O of the other if and only if its base is smaller or equal.

9.2.5 Adding Functions

There are a set of rules that govern combining functions together.

O(f(n)) +O(g(n))!O(max(f(n);g(n))) (9.33)

(f(n)) + (g(n))! (max(f(n);g(n))) (9.34) (f(n)) + (g(n))!(max(f(n);g(n)) (9.35) These statements express the notion that the largest term of the statement is the dominant one. For example,n3+ 2n2+ 3 =O(n3).

Example:Prove thatn2=O(2n).

9-6Lecture 9: November 8, 2018Example:Prove that iff1(n) =O(g1(n)) andf2(n) =O(g2(n)), thenf1(n)+f(n) =O(g1(n)+g2(n)).Example:

f(n) =n+ logn(9.36) g(n) =p(n) (9.37)

Isf(n) =O(g(n)),g(n) =O(f(n)), or both?Example:Iff(n) =n+ logn+pn, nd a simple functiongsuch thatf(n) = (g(n)).

Lecture 9: November 8, 20189-7Summary

f(n) =O(g(n)) meanscg(n) is an upper bound onf(n). Thus there exists some constantcsuch thatf(n) is alwayscg(n), for large enoughn(i.e.,nn0for some constantn0). f(n) = (g(n)) meanscg(n) is a lower bound onf(n). Thus there exists some constantcsuch