Introduction
Growth Functions
Chapter 3
Reading Assignment
p.43-49
p. 50-51: know the definitions of o-notation and ω-notation, that’s all.
p.53-59: know what monotonicity is (p. 53), equation (3.3), (3.8) & (3.9) (p. 54), properties of exponentials (middle of p. 55), and properties of logarithms (second half of p.56). These will not be discussed in class.
2
3
Asymptotic notations of complexity orders
Note: there exists three constants
3
4
Example:
In general,
5
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
6
upper bound
Note: there exists two constants
7
strict upper bound
Note: for all c, there exists n0
8
lower bound
Note: there exists two constants
9
strict lower bound
Note: for all c, there exists n0
10
Theorem 3.1.
For any two functions f(n) and g(n), if and only if and .
11
math you should know
Monotonicity:
A function f is monotonically increasing if m n implies f(m) f(n).
A function f is monotonically decreasing if m n implies f(m) f(n).
A function f is strictly increasing if m < n implies f(m) < f(n).
A function f is strictly decreasing if m > n implies f(m) > f(n).
12
floor and ceiling
13
modular arithmetic
For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a/n :
a mod n =a -a/nn
0≤a mod n≤n
exponentials
a0=1
a1=a
a-1=1/a
am.an=am+n
(am)n=(an)m=amn
14
logarithms
lgn=log2n
lnn=logen where e=2.72
lgkn=(lgn)k
lglgn=lg(lgn)
15
logarithms
for all real a,b,c > 0 and n,
a=blogba
logc(ab)=logca+logcb
logban=nlogba
logba=logca/logcb
logb(1/a)=─logba
logba=1/logab
alogbc=clogba
16
polynomial
17
18
Algorithm Complexity
If T(n)=O(lgkn) for an algorithm, it is a polylogarithmic algorithm.
19
Algorithm Complexity
If T(n)=O(nk) for an algorithm, k≥1, it is a polynomial algorithm.
k=1 is a special case: linear algorithm
k=2 is a special case: quadratic algorithm
20
Polylogarithmic vs. polynomial algorithms
for any constants a,b > 0.
I.e., any positive polynomial function of n grows faster than any polylogarithmic function of n as n increases.
So for large inputs, polylogarithmic algorithms will be more efficient than polynomial algorithms.
21
Exponentials
Exponential functions: a function with a base greater than 1 (e.g. cn where c>1)
If T(n)=O(cn where c>1) for an algorithm, it is an exponential algorithm.
22
Polynomial algorithms v.s. Exponential algorithms
Any exponential function with a base greater than 1 (e.g. cn where c>1) grows faster than any polynomial function nb, where b and c are constants.
So for large inputs, polynomial algorithms will be more efficient than exponential algorithms.
23
Factorials
Factorial function: a function of the form n!
If T(n)=O(n!) for an algorithm, it is an algorithm of factorial complexity.
24
Exponential algorithms v.s. Factorial algorithms
So for large inputs, exponential algorithms with a base of 2 will be more efficient than factorial algorithms.
25
The function nn grows even more quickly than the factorial function. Therefore factorial algorithms will be more efficient than any algorithm with complexity order O(nn).
}
all
for
)
(
)
(
)
(
0
s.t.
,
,
|
)
(
{
))
(
(
0
2
1
0
2
1
n
n
n
g
c
n
T
n
g
c
n
c
c
n
T
n
g
³
£
£
£
$
=
Q
))
(
(
)
(
n
g
n
T
Q
=
)
(
6
.
7
2
3
2
14
2
3
2
2
2
n
n
n>
if
n
n
n
n
Q
¹
£
–
£
f
n
an
bn
c
a, b, c
a>
f(n)=
(n
).
(
)
,
=
+
+
Þ
2
2
0
constants
,
.
Q
).
(n
P(n)
a
a
n
a
n
p
d
d
i
d
i
i
i
Q
=
>
=
å
=
Then
.
0
ith
constant w
are
where
)
(
0
-50
0
50
100
150
200
250
135791113151719
n*n/14
(n*n/2)-3n
n*n/2
Chart1
0.0714285714 -2.5 0.5
0.2857142857 -4 2
0.6428571429 -4.5 4.5
1.1428571429 -4 8
1.7857142857 -2.5 12.5
2.5714285714 0 18
3.5 3.5 24.5
4.5714285714 8 32
5.7857142857 13.5 40.5
7.1428571429 20 50
8.6428571429 27.5 60.5
10.2857142857 36 72
12.0714285714 45.5 84.5
14 56 98
16.0714285714 67.5 112.5
18.2857142857 80 128
20.6428571429 93.5 144.5
23.1428571429 108 162
25.7857142857 123.5 180.5
28.5714285714 140 200
n*n/14
(n*n/2)-3n
n*n/2
Sheet1
1 0.0714285714 -2.5 0.5
2 0.2857142857 -4 2
3 0.6428571429 -4.5 4.5
4 1.1428571429 -4 8
5 1.7857142857 -2.5 12.5
6 2.5714285714 0 18
7 3.5 3.5 24.5
8 4.5714285714 8 32
9 5.7857142857 13.5 40.5
10 7.1428571429 20 50
11 8.6428571429 27.5 60.5
12 10.2857142857 36 72
13 12.0714285714 45.5 84.5
14 14 56 98
15 16.0714285714 67.5 112.5
16 18.2857142857 80 128
17 20.6428571429 93.5 144.5
18 23.1428571429 108 162
19 25.7857142857 123.5 180.5
20 28.5714285714 140 200
Sheet1
n*n/14
(n*n/2)-3n
n*n/2
Sheet2
Sheet3
}
)
(
)
(
0
s.t.
,
|
)
(
{
))
(
(
0
0
n
n
n
cg
n
T
n
c
n
T
n
g
O
³
”
£
£
$
=
))
(
(
)
(
n
g
O
n
T
=
)}
(
)
(
0
,
,
|
)
(
{
))
(
(
0
0
n
cg
n
T
n
n
n
c
n
T
n
g
o
<
£
³
"
$
"
=
))
(
(
)
(
n
g
o
n
T
=
}
)
(
)
(
0
s.t.
,
|
)
(
{
))
(
(
0
0
n
n
n
T
n
cg
n
c
n
T
n
g
³
"
£
£
$
=
W
))
(
(
)
(
n
g
n
T
W
=
)}
(
)
(
0
,
,
|
)
(
{
))
(
(
0
0
n
T
n
cg
n
n
n
c
n
T
n
g
<
£
³
"
$
"
=
w
))
(
(
)
(
n
g
n
T
w
=
f
n
g
n
(
)
(
(
))
=
Q
f
n
O
g
n
(
)
(
(
))
=
f
n
g
n
(
)
(
(
))
=
W
ë
û
é
ù
x
x
x
x
x
-
<
£
£
<
+
1
1
é
ù
ë
û
n
n
n
/
/
2
2
+
=
)
(
log
b
a
n
o
n
=
)
2
(
n
b
o
n
=
)
!
(
2
n
o
n
=
n
o
n
n
!
(
)
=
/docProps/thumbnail.jpeg