Transcript Document

The Growth of Functions
Rosen 2.2
Basic Rules of Logarithms
If logz (x) = a, then x = za
logz (xy)
= logz (x) + logz (y)
logz (x/y)
= logz (x) - logz (y)
logz (xy)
= ylogz (x)
If x = y
then logz (x) = logz (y)
If x < y
then logz (x) < logz (y)
logz (-|x|) is undefined
Growth
• If f is a function from Z or R to R, how can
we quantify the rate of growth and compare
rates of growth of different functions?
• Possible problem: Whether f(n) or g(n) is
larger at any point may depend on value of
n.
For example: n2 > 100n if n > 100
How to quantify growth as n gets bigger?
1200
1000
800
600
400
200
0
-200 0
2
4
6
8
10
12
Big-O Notation
• Let f and g be functions from the set of integers or
the set of real numbers to the set of real numbers.
We say that f(x) is O(g(x)) if there are constants
CN and kR such that
|f(x)|  C|g(x)| whenever x > k.
• We say “f(x) is big-oh of g(x)”.
• The intuitive meaning is that as x gets large, the
values of f(x) are no larger than a constant time the
values of g(x), or f(x) is growing no faster than g(x).
• The supposition is that x gets large, it will approach
a simplified limit.
Show that
3
2
3x +2x +7x+9
is
3
O(x )
Proof: We must show that  constants CN
and kR such that |3x3+2x2+7x+9|  C|x3|
whenever x > k.
Choose k = 1 then
3x3+2x2+7x+9  3x3+2x3+7x3+9x3 = 21x3
So let C = 21.
Then 3x3+2x2+7x+9  21 x3 when x  1.
Show that n! is
n
O(n )
Proof: We must show that  constants CN and
kR such that |n!|  C|nn| whenever n > k.
n! = n(n-1)(n-2)(n-3)…(3)(2)(1)
 n(n)(n)(n)…(n)(n)(n) n times
=nn
So choose k = 0 and C = 1
General Rules
• Multiplication by a constant does not change the
rate of growth. If f(n) = kg(n) where k is a
constant, then f is O(g) and g is O(f).
• The above means that there are an infinite number
of pairs C,k that satisfy the Big-O definition.
• Addition of smaller terms does not change the rate
of growth. If f(n) = g(n) + smaller order terms,
then f is O(g) and g is O(f).
Ex.: f(n) = 4n6 + 3n5 + 100n2 + 2 is O(n6).
General Rules (cont.)
• If f1(x) is O(g1(x)) and f2(x) is O(g2(x)),
then f1(x)f2(x) is O(g1(x)g2(x)).
• Examples:
10xlog2x is O(xlog2x)
n!6n3 is O(n!n3)
=O(nn+3)
Examples
• f(x) = 10 is O(1)
• f(x) = x2 + x + 1 is O(x2)
• f(x) = 2x5 + 100 x3 + xlogx is O(x5)
• f(x) = 2n + n10 is O(2n)
How would you prove this?
Prove that n10 is O(2n )
Proof: We must show that  constants CN and kR
such that |n10|  C|2n| whenever n > k.
Take log2 of both expressions.
log22n = nlog22 =n,
log2n10 = 10log2n
When is 10log2n < n? or n/log2n > 10?
2/1 = 2,
4/2 = 2,
8/3  2.67, 16/4 = 4
32/5 = 6.2,
64/6  10.67
For n = 64, 264 > 6410. So, if we choose then k = 64, C =
1, then |n10|  1*|2n| whenever n > 64.
Example: Big-Oh Not Symmetric
• Order matters in big-oh. Sometimes f is
O(g) and g is O(f), but in general big-oh is
not symmetric.
Consider f(n) = 4n and g(n) = n2. f is O(g).
• Can we prove that g is O(f)? Formally, 
constants CN and kR such that |n2| 
C|4n| whenever n > k?
• No. To show this, we must prove that
negation is true for all C and k. CN,
kR, n>k such that n2 > C|4n|.
CN, kR, n>k such that n2 > 4nC.
• To prove that negation is true, start with
arbitrary C and k. Must show/construct an
n>k such that n2 > 4nC
• Easy to satisfy n > k, then
• To satisfy n2>4nC, divide both sides by n to
get n>4C. Pick n = max(4C+1,k+1), which
proves the negation.
10000
9000
8000
7000
n*n
6000
4n
5000
5*4n
4000
10*4*n
3000
20*4*n
2000
1000
0
0
20
40
60
80
100
Is
n
2
O(n!)?
We must show that  constants CN and kZ
such that |2n|  C|n!| whenever n > k.
2n = 2(2)(2)…(2)(2)(2) n times
 n(n-1)(n-2)…(3)(2)(1) =n! if n = 4
So let C = 1 and k = 3.
Is
n
2
O(n!)?
Note that we could also choose k = 1 and C =
2
Since
|20|  2*|0!| = 2
|21|  2*|1!| = 2
|22|  2*|2!| = 4
|23|  2*|3!|= 12
Is
2
f(x)=(x +1)/(x+1)
O(x)?
We must show that  constants CN and kR
such that |f(x)|  C|x| whenever x > k.
x 2  1 x 2  1  2 ( x  1)( x  1)  2



x 1
x 1
x 1
2
x 1
x
When x > 1 (Why?)
x 1
Therefore let k=1, C = 1
|(x2+1)/(x+1)|  |x| when x > 1
Hierarchy of functions
nn nlog n n
n
2
n
2
1
n!
n2
n3
3n
log2n
nn
Hierarchy of functions
1
nn nlog n
2
n2
n3
n!
n
3n
n
log2n
2n
nn
Hierarchy of functions
1, log2n
nn nlog n
2
n2
n3
n!
n
3n
n
2n
nn
Hierarchy of functions
1, log2n, 3n
nn nlog n
2
n2
n3
n!
n
n
2n
nn
Hierarchy of functions
1, log2n, 3n, n
nn nlog n
2
n2
n3
n!
n
2n
nn
Hierarchy of functions
1, log2n, 3n, n, n
nn nlog n
2
n2
n3
n!
2n
nn
Hierarchy of functions
1, log2n, 3n, n, n, nlog2n
nn
n2
n3
n!
2n
nn
Hierarchy of functions
1, log2n, 3n, n, n, nlog2n, nn
n2
n3
n!
2n
nn
Hierarchy of functions
1, log2n, 3n, n, n, nlog2n, nn, n2
n!
n3
2n
nn
Hierarchy of functions
1, log2n, 3n, n, n, nlog2n, nn, n2, n3
n!
2n
nn
Hierarchy of functions
1, log2n, 3n, n, n, nlog2n, nn, n2, n3, 2n
n!
nn
Hierarchy of functions
1, log2n, 3n, n, n, nlog2n, nn, n2, n3, 2n, n!, nn
Each one is Big-Oh of any function to its right
Prove that log10x is O(log2x)
First we will prove the following lemma:
Lemma: log10x = clog2x where c is a
constant.
Proof:
Let y = log2x.
Then 2y = x and log102y = log10x.
log102y = ylog102 = log10x. But since y =
log2x, this means that
log2xlog102 = log10x. Therefore c = log102
To Prove that log10x is O(log2x)
We must show that  constants CN and kR
such that |log10x|  C|log2x| whenever x >
k.
From the lemma log102log2x = log10x; so
choose C = log102, k=0
Prove log(n!) is O(nlogn)
We must show that  constants CN and kR
such that |logn!|  C|nlogn| whenever x > k.
We know that n!  nn so
log(n!)  log(nn)= nlogn
So choose k = 1, C = 1
Time Complexity
We can use Big-O to find the time complexity of
algorithms (i.e., how long they take in terms of the
number of operations performed).
There are two types of complexity normally considered.
• Worst-case complexity. The largest number of
operations needed for a problem of a given size in the
worst case. The number of operations that will
guarantee a solution.
• Average-case complexity. The average number of
operations used to solve a problem over all inputs of a
given size.
Complexity of the Linear Search
Algorithm
Worst-case complexity
• The algorithm loops over all the values in a list of n
values.
– At each step, two comparisons are made. One to see whether
the end of the loop is reached, and one to compare the search
element x with the element in the list.
– If x is equal to list element ai, then 2i comparisons are made.
– If x is not in the list, then 2n comparisons are made.
– The worst-case complexity is thus 2n and is O(n).
Complexity of the Linear Search
Algorithm
Average-case complexity
• The algorithm loops over all the values in a list of n
values.
– At each step, two comparisons are again made.
– On average, the number of comparisons is
2 + 4 + 6 +….+ (2n)
n
What’s the numerator?
n(n  1)
2(  k 
)
2
k 1
Average case is O(n)
n
Complexity of Pair-wise
Correlation
Assume that there are n elements to correlate