代写代考 COMP 3711 Design and Analysis of Algorithms

COMP 3711 Design and Analysis of Algorithms
Tutorial 1: Asymptotic Notation

Asymptotic Notation: Quick Revision

Copyright By PowCoder代写 加微信 powcoder

Upper bounds.
ifexistconstants𝑐>0and𝑛00suchthatforall𝑛𝑛0, 𝑇 𝑛 ≤𝑐·𝑓(𝑛).
Equivalent definition: lim sup 􏰂 􏰀 < ∞ . 􏰀→􏰁 􏰃􏰀 Lower bounds.  ifexistconstants𝑐>0and𝑛00suchthatforall𝑛𝑛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 ni1    1    ( j  i  1)    k
i1 ji ki i1 ji i1 k1
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:
cn2n kcn2 c’n3n k2c’n3
n ni1 n n
kc (ni1)2 c 
j2 cc’ n3 (n3) 22
j2 cc’n3 (n3) 11
i1 k1 i1 n ni1 n
kc(ni1)2 c 11
i1 k1 i1 n ni1
Therefore:   k  (n3 ) i1 k1

Recursion Exercise

Recursion Exercise
􏰈 􏰒􏰓􏰈 􏰒􏰓􏰆 􏰒
􏰈 􏰒􏰓􏰈 􏰒􏰓􏰆 􏰒
Geometric progression –
1 − 2􏰓􏰖􏰗􏰘􏰊􏰀
=𝑛 1 +𝑇1=𝑛21−𝑛 +𝑇1

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com