COMP 3711 Design and Analysis of Algorithms
Tutorial 1: Asymptotic Notation
Asymptotic Notation: Quick Revision
Copyright By PowCoder代写 加微信 powcoder
Upper bounds.
ifexistconstants𝑐>0and𝑛00suchthatforall𝑛𝑛0, 𝑇 𝑛 ≤𝑐·𝑓(𝑛).
Equivalent definition: lim sup < ∞ . →
Lower bounds. ifexistconstants𝑐>0and𝑛00suchthatforall𝑛𝑛0, 𝑇 𝑛 ≥𝑐·𝑓(𝑛).
Equivalent definition: lim inf > 0 . →
Tight bounds.
if 𝑇 𝑛 = 𝑂(𝑓(𝑛))and 𝑇 𝑛 = (𝑓(𝑛)).
Note: Here “=” means “is”, not equal.
More mathematically correct expression should be 𝑇 𝑛 ∈ 𝑂 𝑓 𝑛 .
constant < logarithmic < polynomial < exponential < < .< < <
Some Basic Properties
a) Iff and b) Iff and
c) Iff and
d) Iff and e) Iff and
f) Iff and
Question 1
For each of the following statements, answer whether the statement is true or false.
Question 2
Suppose and . Which of the following are true? Justify your answers.
Question 2
Suppose and Is the following true?
This was just basic property (d).
Question 2
Suppose and . Is the following true?
Counterexample: Set , . ,
Use the same counterexample as in part (b).
Question 3
Let be a function. Suppose that, for all
(a) For fixed is
(b) Define Is
Question 3: (a)
(a) For fixed is Yes. Recall where, for each
We know (basic property (d)) that
if and then
(a) For fixed 𝑘, is 𝑔 𝑛 = 𝑂 𝑓 𝑛 ?
Iterating, using induction, shows that, for FIXED k
Question 3:
(b) where, for each
Even though we just saw that, for FIXED
It is NOT true that or even that
We display a counterexample.
A Counterexample
=> for all FIXED =>
=> where => So, for fixed
Which we also know is true from part (a)
In particular,
is NOT or even
A Deeper Dive
Suppose that for all and set (a) (b)
IS NOT CORRECT. Why is this “proof” wrong?
Use the counterexample from previous page to unpack problem.
Set , and
The problem is that equalities (a) and (b) aren’t mathematically well defined. notation has a multiplicative constant associated with it, i.e.,
writing implies there is a constant s.t.
The way that (a) and (b) are written imply that all of the constants are the same. But they are NOT. so the constants are increasing.
Exercise On the Running Time of Triple Nested Loops
for i = 1 to n
for j = i to n
for k = i to j
do one unit of work
Prove that the above code performs units of work. Use the fact that 𝑐 , (polynomial series, reviewed in Lecture 0).
The total amount of work is:
n n j n n n ni1 1 ( j i 1) k
i1 ji ki i1 ji i1 k1
Problem has now been transformed into proving that
k (n3 )
Exercise On the Running Time of Triple Nested Loops (cont)
Recall (from exercise in first lecture) that 𝑐 for c=1 this is the arithmetic series, for c>1 this is the polynomial series). Thus, by the definition of , there exist constants c1, c2, c’1, c’2, such that:
cn2n kcn2 c’n3n k2c’n3
n ni1 n n
kc (ni1)2 c
j2 cc’ n3 (n3) 22
j2 cc’n3 (n3) 11
i1 k1 i1 n ni1 n
kc(ni1)2 c 11
i1 k1 i1 n ni1
Therefore: k (n3 ) i1 k1
Recursion Exercise
Recursion Exercise
Geometric progression –
1 − 2
=𝑛 1 +𝑇1=𝑛21−𝑛 +𝑇1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com