COMP 3711 Design and Analysis of Algorithms

Tutorial 1: Asymptotic Notation

 Asymptotic Notation: Quick Revision
Upper bounds. 𝑇 𝑛 = 𝑂(𝑓(𝑛))
if exist constants 𝑐 > 0 and 𝑛0 ³ 0 such that for all 𝑛 ³ 𝑛0, 𝑇 𝑛 ≤ 𝑐 · 𝑓(𝑛).
$ !
Equivalent definition: lim sup % !
< ∞.
!→#

Lower bounds. 𝑇 𝑛 = W(𝑓(𝑛))

if exist constants 𝑐 > 0 and 𝑛0 ³ 0 such that for all 𝑛 ³ 𝑛0, 𝑇 𝑛 ≥ 𝑐 · 𝑓(𝑛).
$ !
Equivalent definition: lim inf %
!
> 0.
!→#

Tight bounds. 𝑇 𝑛 = Q(𝑓(𝑛))

if 𝑇 𝑛 = 𝑂(𝑓(𝑛)) and 𝑇 𝑛 = W(𝑓(𝑛)).

Note: Here “=” means “is”, not equal.

More mathematically correct expression should be 𝑇 𝑛 ∈ 𝑂 𝑓 𝑛 .

constant < logarithmic < polynomial < exponential

&&&&
9999!!!! < log"# 𝑛 < 𝑛#." < 𝑛 log 𝑛< 𝑛% < 2&

2
 Some Basic Properties

a) If f 𝑛 = 𝑂(𝑔 𝑛 ) and 𝑔 𝑛 = 𝑂 ℎ 𝑛 ⇒ 𝑓 𝑛 = 𝑂(ℎ 𝑛 )

b) If f 𝑛 = Ω(𝑔 𝑛 ) and 𝑔 𝑛 = Ω ℎ 𝑛 ⇒ 𝑓 𝑛 = 𝛺(ℎ 𝑛 )

c) If f 𝑛 = Θ(𝑔 𝑛 ) and 𝑔 𝑛 = Θ ℎ 𝑛 ⇒ 𝑓 𝑛 = Θ(ℎ 𝑛 )

d) If f 𝑛 = 𝑂(ℎ 𝑛 ) and 𝑔 𝑛 = 𝑂 ℎ 𝑛 ⇒ 𝑓 𝑛 + 𝑔(𝑛) = 𝑂(ℎ 𝑛 )

e) If f 𝑛 = Ω(ℎ 𝑛 ) and 𝑔 𝑛 = Ω ℎ 𝑛 ⇒ 𝑓 𝑛 + 𝑔(𝑛) = Ω(ℎ 𝑛 )

f) If f 𝑛 = Θ (ℎ 𝑛 ) and 𝑔 𝑛 = Θ ℎ 𝑛 ⇒ 𝑓 𝑛 + 𝑔(𝑛) = Θ(ℎ 𝑛 )

3
 Question 1
For each of the following statements, answer whether the
statement is true or false.

a) 1000𝑛( + 1000𝑛 = 𝑂(𝑛)) True

b) 𝑛( − 𝑛 = Θ(𝑛) False

c) 𝑛𝑙𝑜𝑔 𝑛 = 𝑂(𝑛() True

d) 𝑛𝑙𝑜𝑔 𝑛 = Θ(𝑛() False

*
e) +,,
= 𝛺(𝑛) True

f) 12𝑛 + 2* + 𝑛) = 𝑂 𝑛) False

g) 2𝑛𝑙𝑜𝑔 𝑛 + 𝑛 = Θ(𝑛𝑙𝑜𝑔𝑛) True

4
 Question 2

Suppose 𝑇+ 𝑛 = 𝑂 𝑓 𝑛 and 𝑇( 𝑛 = 𝑂 𝑓 𝑛 . Which of

the following are true? Justify your answers.

(a) 𝑇+ 𝑛 + 𝑇( 𝑛 = 𝑂 𝑓 𝑛

-! *
(b) -" *
=𝑂 1

(c) 𝑇+ 𝑛 = 𝑂 𝑇( 𝑛
 Question 2
Suppose 𝑇+ 𝑛 = 𝑂 𝑓 𝑛 and 𝑇( 𝑛 = 𝑂 𝑓 𝑛 .
Is the following true?

(a) 𝑇+ 𝑛 + 𝑇( 𝑛 = 𝑂 𝑓 𝑛 ? True.

This was just basic property (d).

Example
𝑇+ 𝑛 = 2𝑛. + 3𝑛) and 𝑇( 𝑛 = 5𝑛. + 2𝑛(

𝑇+ 𝑛 = O(𝑛.) and 𝑇( 𝑛 = O(𝑛.)

⇒ 𝑇+ 𝑛 + 𝑇( 𝑛 = O 𝑛.
 Question 2
Suppose 𝑇+ 𝑛 = 𝑂 𝑓 𝑛 and 𝑇( 𝑛 = 𝑂 𝑓 𝑛 .
Is the following true?
-! *
(b) -" *
=𝑂 1 ? False.

Counterexample: Set 𝑇+ 𝑛 = 𝑛(, 𝑇( 𝑛 = 𝑛, 𝑓 𝑛 = 𝑛(.

⇒ 𝑇+ 𝑛 = 𝑂 𝑓 𝑛 , 𝑇( 𝑛 = 𝑂 𝑓 𝑛
-! *
but -" *
= 𝑛 ≠ 𝑂(1)

(c) 𝑇+ 𝑛 = 𝑂 𝑇( 𝑛 ? False.

Use the same counterexample as in part (b).

𝑛( ≠ O(𝑛)
 Question 3
Let 𝑓(𝑛) be a function.
Suppose that, for all 𝑖 > 0, 𝑇/ (𝑛) = 𝑂 𝑓 𝑛 .
Define 𝑔0 * = ∑0/1+ 𝑇/ 𝑛

(a) For fixed 𝑘, is 𝑔0 𝑛 = 𝑂 𝑓 𝑛 ?

(b) Define 𝑔 𝑛 = 𝑔* 𝑛 .
Is 𝑔 𝑛 = 𝑂 𝑓 𝑛 ?
Is 𝑔 𝑛 = 𝑂 𝑛𝑓 𝑛 ?

8
 Question 3: (a)
(a) For fixed 𝑘, is 𝑔0 𝑛 = 𝑂 𝑓 𝑛 ? Yes.

Recall 𝑔0 (𝑛) = ∑0/1+ 𝑇/ 𝑛 where, for each 𝑖, 𝑇/ 𝑛 = 𝑂 𝑓 𝑛 .

We know (basic property (d)) that

if 𝑈 𝑛 = 𝑂 𝑓 𝑛 and 𝑉 𝑛 = 𝑂 𝑓 𝑛 then (𝑈 𝑛 + 𝑉 𝑛 ) = 𝑂(𝑓 𝑛 )

Then 𝑔( 𝑛 = 𝑇+ 𝑛 + 𝑇( 𝑛 = 𝑂 𝑓 𝑛

Iterating, using induction, shows that, for FIXED k

𝑔0 𝑛 = 𝑔02+ 𝑛 + 𝑇0 𝑛 = 𝑂(𝑓 𝑛 )

𝑈(𝑛) 𝑉(𝑛)
9
 Question 3:
(b) 𝑔0 (𝑛) = ∑0/1+ 𝑇/ 𝑛 where, for each 𝑖, 𝑇/ 𝑛 = 𝑂 𝑓 𝑛 .
*
g 𝑛 = 𝑔* 𝑛 = E 𝑇/ 𝑛
/1+

Even though we just saw that, for FIXED 𝑘, 𝑔0 𝑛 = 𝑂 𝑓 𝑛 ,

It is NOT true that 𝑔 𝑛 = 𝑂 𝑓 𝑛

or even that 𝑔 𝑛 = 𝑂 𝑛𝑓 𝑛 .

We display a counterexample.

10
 A Counterexample
Set 𝑇3 𝑛 = 𝑖 ⋅ 𝑛, and 𝑓 𝑛 = 𝑛.

=> 𝑇/ 𝑛 = 𝑂(𝑓 𝑛 ) for all FIXED 𝑖 ≥ 1.

0(04+)
=> 𝑔0 𝑛 = ∑0/1+ 𝑇/ (𝑛) = ∑0/1+ 𝑖 ⋅ 𝑛 = 𝑛 (

0(04+)
=> 𝑔0 𝑛 = 𝑐0 𝑛 where 𝑐0 = ( Which we also know is
true from part (a)
=> So, for fixed 𝑘, 𝑔0 𝑛 = 𝑂(𝑛)

*(*4+)
But g 𝑛 = 𝑔* 𝑛 = 𝑛 ( = Θ(𝑛))
In particular,
𝑔(𝑛) is NOT 𝑂(𝑓 𝑛 ) or even 𝑂 𝑛 𝑓 𝑛 !

𝑂(𝑛) 𝑂(𝑛') 11
 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

n n -i +1

åå
i =1 k =1
k = Q( n 3 )

12
 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:
n n
c ×n £ åk £ c ×n
1
2
2
2
c' ×n £ åk £ c' ×n
1
3 2
2
3

k =1 k =1
Then:

n n -i +1 n n

åå
i =1 k =1
k ³ å c1 × (n - i + 1) 2 ³ c1 å j 2 ³ c1c '1 n3 = W(n3 )
i =1 j =1
n n -i +1
Therefore: å å k = Q( n )
i =1 k =1
3

13
Recursion Exercise

𝑛
𝑇 𝑛 =𝑛+𝑇
2
𝑛 𝑛
=𝑛+ +𝑇 %
2 2
𝑛 𝑛 𝑛
=𝑛+ + %+𝑇 '
2 2 2
When does it stop?
𝑛
𝑇 1 = 1, 𝑇 ? =1
2
ℎ = 𝑙𝑜𝑔% 𝑛
14
 Recursion Exercise
𝑛 𝑛 𝑛 𝑛 𝑛
=𝑛+ + ) + … + *+) + *+$ + 𝑇( * )
2 2 2 2 2
1 1 1 1 𝑛
= 𝑛(1 + + ) + … + *+) + *+$ ) + 𝑇( * )
2 2 2 2 2

+2>#$!
Sum of geometric series 𝑎 + 𝑎𝑟 + 𝑎𝑟 ' … =𝑎
+2>

1*
1− 1 − 2+*
=𝑛 2 +𝑇 1 =𝑛 +𝑇 1 =
1 1
1− 1−
2 2

1 − 2)*+,!! 1
=𝑛 +𝑇 1 =𝑛 2 1− +𝑇 1
1 𝑛
2

= 2𝑛 − 2 + 1 = 2𝑛 − 1
𝑇 𝑛 = 𝑂(𝑛)
15