Introduction to Algorithms - Northeastern University
CS 5002: Discrete Structures
Lecture 9: November 8, 2018 1
Instructors: Adrienne Slaughter, Tamara Bonaci
Fall 2018
Disclaimer: 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, Matrices
9.1 Overview
Objective: Introduce algorithms. 1. Review logarithms 2. Asymptotic analysis 3. Define Algorithm 4. How to express or describe an algorithm 5. Run time, space (Resource usage) 6. Determining Correctness 7. Introduce representative problems
1. foo
9.2 Asymptotic Analysis
The goal with asymptotic analysis is to try to find a bound, or an asymptote, of a function. This allows us to come up with an "ordering" of functions, such that one function is definitely bigger than another, in order to compare two functions. We do this by considering the value of the functions as n goes to infinity, so for very large values of n, as opposed to small values of n that 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-2
Lecture 9: November 8, 2018
4096 2048 1024 512 256 128
64 32 16 8 4 2 1
Growth of Functions nn n!
2n
n2 n log(n)
n
n
log(n)
1
2
3
4
5
6
7
8
From this chart, we see:
1
log n
n
n
n log(n)
n2
2n
n!
nn
Complexity
(1) (log n) (n) (n log n) nb (bn) (where b > 1) (n!)
Terminology Constant
Logarithmic Linear
Linearithmic Polynomial Exponential
Factorial
9.2.1 Big-O: Upper Bound
(9.1)
Definition 9.1 (Big-O: Upper Bound) f (n) = O(g(n)) means there exists some constant c such that f (n) c ? g(n), for large enough n (that is, as n ). We say f (n) = O(g(n))
Example: I claim 3n2 - 100n + 6 = O(n2). I can prove this using the definition of big-O:
Lecture 9: November 8, 2018
9-3
f (n) = 3n2 - 100n + 6 g(n) = n2
3n2 - 100n + 6 c ? n2 for some c If c = 3 : 3n2 - 100n + 6 3n2
To prove using Big-O: ? Determine f (n) and g(n) ? Write the equation based on the definition ? Choose a c such that the equation is true. ? If you can find a d, then f (n) = O(g(n)). If not, then f (n) = O(g(n)).
These statements are all true:
3n2 - 100n + 6 = O(n2) 3n2 - 100n + 6 = O(n3) 3n2 - 100n + 6 = O(n)
Proving 9.7:
(9.2) (9.3) (9.4) (9.5)
(9.6) (9.7) (9.8)
f (n) = 3n2 - 100n + 6 g(n) = n3 3n2 - 100n + 6 = c ? n3 (for some c) If c = 1 : 3n2 - 100n + 6 n3 (when n > 3)
(9.9) (9.10) (9.11) (9.12)
We also know this to be true because order is transitive: if f (n) = O(g(n)), and g(n) = O(h(n)), then f (n) = O(h(n)). Since n2 = O(n3), then any f (n) = O(n2) is also O(n3).
Proving 9.8:
f (n) = 3n2 - 100n + 6 g(n) = n For any c : cn < 3n2 (when n > c)
9.2.2 Big-Omega: Lower Bound
(9.13) (9.14) (9.15)
Definition 9.2 (Big-Omega: Lower Bound) f (n) = (g(n)) means there exists some constant c such that f (n) c ? g(n), for large enough n (that is, as n ).
We say f (n) = (g(n)) or "f of n is Big Omega of g of n"
9-4
Lecture 9: November 8, 2018
Example: I claim 3n2 - 100n + 6 = (n2). I can prove this using the definition of big-Omega:
f (n) = 3n2 - 100n + 6 g(n) = n2
3n2 - 100n + 6 c ? n2 for some c If c = 2 : 3n2 - 100n + 6 2n2
We show Big-Omega the same way we show Big-O. These statements are all true:
3n2 - 100n + 6 = (n2) 3n2 - 100n + 6 = (n3) 3n2 - 100n + 6 = (n)
Proving 9.21:
(9.16) (9.17) (9.18) (9.19)
(9.20) (9.21) (9.22)
Proving 9.22:
f (n) = 3n2 - 100n + 6 g(n) = n3 3n2 - 100n + 6 c ? n3 (for some c) If c = 1 : 3n2 - 100n + 6 n3 (when n > 3)
(9.23) (9.24) (9.25) (9.26)
f (n) = 3n2 - 100n + 6 g(n) = n For any c : cn < 3n2 (when n > 100c)
9.2.3 Big-Theta: "Tight" Bound
(9.27) (9.28) (9.29)
Definition 9.3 (Big-Theta: "Tight" Bound) f (n) = (g(n)) means there exists some constants c1 and c2 such that f (n) c1g(n) and f (n) c2g(n). We say f (n) = (g(n)) or "f of n is Big-Theta of g of n".
Definition 9.4 (Theta and "order of ") When f (x) = (g(x)), it is the same as saying f (x) is the order of g(x), or that f (x) and g(x) are the same order.
3n2 - 100n + 6 = (n2) Both O and apply
Lecture 9: November 8, 2018
9-5
3n2 - 100n + 6 = (n3) Only O applies 3n2 - 100n + 6 = (n) Only applies
Interesting Aside Donald Knuth popularized the use of Big-O notation. It was originally inspired
by the use of "ell" numbers, written as L(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 know L(5) < 100, for example.
Theorem 9.5 If f (x) = anxn + an-1xn-1 + ? ? ? + a1x + a0, then f (x) = O(n)
a) f (x) = 17x + 11
c) f (x) = x log x e) f (x) = 2x
b) f (x) = x2 + 1000 d) f (x) = x4/2
f) f (x) = x ? x
9.2.4 Logs, Powers, Exponents
We've seen f (n) = O(nd). If d > c > 1, then nc = O(nc). nc is O nd , but nd is not O (nc). logb n is O(n) whenever b > 1. Whenever b > 1, c and d are positive:
(logb n)c is O nd , but nd is not (O (logb n)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
nd is O (bn) , but bn is not O nd
(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,
bn is O (cn) but cn is not O (bn)
(9.32)
This tells us that if we have two exponential functions with different 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))) (f (n)) + (g(n)) (max(f (n), g(n))) (f (n)) + (g(n)) (max(f (n), g(n))
(9.33) (9.34) (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 that n2 = O(2n).
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
Related searches
- introduction to financial management pdf
- introduction to finance
- introduction to philosophy textbook
- introduction to philosophy pdf download
- introduction to philosophy ebook
- introduction to marketing student notes
- introduction to marketing notes
- introduction to information systems pdf
- introduction to business finance pdf
- introduction to finance 15th edition
- introduction to finance books
- introduction to finance online course