CSCI 3160

Tutorial 1
Big-O Notation & Pseudocode
PANG Ho Lam
PANG Ho Lam
▪ Email: hlpang@cse.cuhk.edu.hk
▪ Office: SHB 121A
▪ Office hour: Tuesday 3:30 pm – 5:30 pm

▪ Any question: come at my office hour, or contact me to

make an appointment.
Today’s topic
1. Big-O notation
2. Pseudocode
Big-O Notation
▪ Commonly used to express time complexity when
evaluating the performance of algorithms.
▪ We want to express running time as a function of instance
size, 𝑇 𝑛 , regardless of some hardware differences, etc..
▪ How 𝑇 𝑛 grows with 𝑛?
Big-O Notation
▪ 𝑇 𝑛 = 𝑂 𝑔 𝑛 𝑖𝑓 𝑡ℎ𝑒𝑟𝑒 𝑎𝑟𝑒 𝑠𝑜𝑚𝑒 𝑐, 𝑛0 , 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑇 𝑛 ≤ 𝑐 ∙
𝑔 𝑛 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑛 > 𝑛0 .
▪ (Intuitively) The growing speed of 𝑇 𝑛 is not faster than
𝑔 𝑛 .
Examples
Suppose a is an array of size n, say, [3, 4, 7, 1, 11, … , 8]
Algorithm_1_Print(array a)
if a[2]=4 then print a[2] 𝑇 𝑛 =𝑐
=𝑂 1

Algorithm_2_Max(array a)
max ← a[0], n ← length(a) 𝑇 𝑛 = 𝑐1 𝑛 + 𝑐2
for i ← 1 to n-1 do =𝑂 𝑛
if a[i] > max then max ← a[i]
end for
print max
Examples
Suppose a is an array of size n, say, [3, 4, 7, 1, 11, … , 8]
Algorithm_3_Loop(array a) 𝑇 𝑛 = 𝑛 𝑛 𝑐1 𝑛 + 𝑐2
for i ← 1 to n-1 do
for j ← 1 to n-1 do = 𝑂 𝑛3 = 𝑛2 𝑂 𝑛
Algorithm_2_Max(a)

Algorithm_4_Concat(array a) 𝑇 𝑛 = 𝑛 𝑛 𝑐1 𝑛 + 𝑐2 +
Algorithm_2_Max(a) 𝑐1 𝑛 + 𝑐2
Algorithm_3_Loop(a)
= 𝑂 𝑛3 = 𝑂 𝑛3 + 𝑛
Examples
Target: 10
Suppose a is a sorted array of size n
[1, 2, 4, 5, 6, 7, 8, 9]
Binary_search(array a, number target)
low ← 0
high ← length(a) [6, 7, 8, 9]
while low ≤ high do
mid ← (low + high)/2
if target>a[mid] then low ← mid+1
[8, 9]
if target<a[mid] then high ← mid-1
if target=a[mid] then [9]
print(“FOUND”)
terminate
end while 𝑇 𝑛 = 𝑐 + 𝑇 𝑛/2
print(“NOT FOUND”) = 𝑂 log 𝑛
Comparing complexities
1 2 𝑛
𝑂 1 , … , log log 𝑛 , … , log 𝑛 , log 𝑛 , … , 𝑛2 , 𝑛, 𝑛2 , … , 2𝑛 , 2𝑛 , … , 22 , …
2

<--- faster ---- ----slower--->

▪ We compare two complexities by the above classification
and by dominating terms.
▪ Non-dominating terms are insignificant when n is large.
▪ e.g.
𝑂 4𝑛 𝑛3 > 𝑂 2𝑛 𝑛9
𝑂 4𝑛 > 𝑂 3.99𝑛 log 𝑛
Examples
▪ 2𝑛 𝑛1/3 log 𝑛 = 𝑂 2𝑛 𝑛1/3 log log 𝑛 ? No

▪ 𝑛1.001 = 𝑂 𝑛 log 2𝑛 ? No

▪ 𝑛3 = 𝑂 2𝑛 + 𝑛 ? Yes
Other Asymptotic Notations
▪ We may want a “lower bound” notation and a “tight bound”
notation.
2𝑛 𝑛1/3 log 𝑛 = Ω 2𝑛 𝑛1/3 log log 𝑛
▪ Big-omega, Ω
𝑛1.001 = Ω 𝑛 log 2𝑛
▪ Basically the inverse of big-o notation
▪ 𝑇 𝑛 =𝑂 𝑔 𝑛 ⟺ 𝑔 𝑛 =Ω 𝑇 𝑛

▪ Big-theta, 𝜃
▪ 𝑂+Ω
▪ 𝑇 𝑛 =𝜃 𝑔 𝑛 ⟺ 𝑇 𝑛 =𝑂 𝑔 𝑛 𝑎𝑛𝑑 𝑇 𝑛 = Ω 𝑔 𝑛
▪ 4𝑛2 + 𝑛 = 𝑂 𝑛2 , 4𝑛2 + 𝑛 = Ω 𝑛2 ⇒ 4𝑛2 + 𝑛 = 𝜃 𝑛2
Polynomial vs Exponential
▪ Algorithms running in exponential time may take hours to
complete a task, while algorithms running in polynomial time
may take seconds only.
▪ Polynomial vs Exponential in input size.
▪ In some cases, the input size is denoted by n, e.g., an n-
digit number, an array of n element, etc..
▪ In other cases, the input size is not explicitly stated.
Polynomial vs Exponential –
Fibonacci
Fibonacci (integer k)
F[0] ← 1, F[1] ← 1.
For i = 2 to k,
F[i] ← F[i-1] + F[i-2].
Output F[k].

Time complexity
𝑇 𝑘 = #𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠 ∙ Time for each iteration
= 𝑘 ∙ Time for computing F i − 1 + F i − 2 ≈ 𝑘 ∙ 𝑂 𝑘 = 𝑂 𝑘 2 .

• In the worst case, F[i] would get one more digit after each addition.
• Adding up two i-digit numbers needs O(i) time.
Polynomial vs Exponential –
Fibonacci
Fibonacci (integer k) Input value: k
Input size: O(log k)
F[0] ← 1, F[1] ← 1.
For i = 2 to k, We need only O(log k) bits of
F[i] ← F[i-1] + F[i-2]. memory space to store integer k
Output F[k].

Time complexity
𝑇 𝑘 = #𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠 ∙ Time for each iteration
= 𝑘 ∙ Time for computing F i − 1 + F i − 2 ≈ 𝑘 ∙ 𝑂 𝑘 = 𝑂 𝑘 2 .

• However… this is not polynomial time.

Polynomial vs Exponential –
Fibonacci
Fibonacci (integer 2s) Input value: up to 2s in the worst
case
F[0] ← 1, F[1] ← 1. Input size: s
For i = 2 to 2s,
F[i] ← F[i-1] + F[i-2]. We need only O(s) bits of
Output F[2s]. memory space to store integer 2s

Time complexity
𝑇 2𝑠 = #𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠 ∙ Time for each iteration
= 2𝑠 ∙ Time for computing F i − 1 + F i − 2 ≈ 2𝑠 ∙ 𝑂 2𝑠 = 𝑂 22𝑠 .

• Time complexity is exponential in s (the input size)

Polynomial vs Exponential –
Multiplication
Product (integer x,y) * Assume x,y have n digits.

Product ← 0.
For i ← 1 to y,
product ← product + x.
Output product.

Time complexity
𝑇 𝑘 = #iterations ∙ Time for each iteration
= 𝑦 ∙ Time for computing product + x = 𝑦 ∙ 𝑂 𝑛 = 2𝑛 ∙ 𝑂 𝑛 = 𝑂 2𝑛 𝑛

• Notice that this time, x, y are input values, and n is input size.
Polynomial vs Exponential –
More Confusions…
Problem 1: Given an array of n integers, find
the element with value closest to integer k.
Problem 2: Given an array of n integers, find
the k-th largest element.
Algorithm A: Solving both problems in O(nk)
time.

Is A polynomial-time for Problem 1?

Is A polynomial-time for Problem 2?

Polynomial vs Exponential –
More Confusions…
Problem 1: Given an array of n integers, find
the element with value closest to integer k.
Problem 2: Given an array of n integers, find
the k-th largest element.
Algorithm A: Solving both problems in O(nk)
time.

Problem 1 has input size

Is A polynomial-time for Problem 1? NO 𝑂(𝑛 + log 𝑘)

Problem 2 implies 𝑘 < 𝑛,

Is A polynomial-time for Problem 2? YES
so A runs in time 𝑂 𝑛2
Pseudocode
▪ No strict syntax.
▪ Human readable and explains idea clearly.
▪ Does not need to be very low level, unless it is implied.

if a>b then swap a and b

if a>b then
temp ← a
a ← b
b ← temp
Common Structures –
Conditional statements
▪ if B then S1 else S2 ▪ case B1
S1
▪ if B then case B2
S1 S2
else otherwise
S2 S3
endif
▪ case var of
B1: S1
B2: S2
otherwise: S3
endcase
Common Structures –
Iterations
▪ while B do S
▪ for i ← 1 to 10 do S
endfor
▪ repeat
S
until B
Examples –
Binary Search
Target: 10
Suppose a is a sorted array of size n
[1, 2, 4, 5, 6, 7, 8, 9]
Binary_search(array a, number target)
low ← 0
high ← length(a) [6, 7, 8, 9]
while low ≤ high do
mid ← (low + high)/2
if target>a[mid] then low ← mid+1
[8, 9]
if target<a[mid] then high ← mid-1
if target=a[mid] then [9]
print(“FOUND”)
terminate
end while 𝑇 𝑛 = 𝑐 + 𝑇 𝑛/2
print(“NOT FOUND”) = 𝑂 log 𝑛
Examples –
Binary Search
Suppose a is a sorted array of size n

Binary_search(array a, interger low, integer high, number target)

if low>high then
print(“NOT FOUND”)
terminate
if a[mid] = target then
print(“FOUND”)
terminate
mid ← (low + high)/2
if a[mid]<target then
Call Binary_search(a, mid+1, high, target)
if a[mid]>target then
Call Binary_search(a, low, mid-1, target)
Examples –
Binary Search
Suppose a is a sorted array of size n

Binary_search(array a, number target)

m ← the middle element of a.

If m = target, then:
Report “FOUND” and terminate the algorithm.
Else if m is the only element of a, then:
Report “NOT FOUND” and terminate the algorithm.
Else:
Split the array at m into two equal halves, a smaller
half and a larger half.
If m > target, then:
Recursively call this algorithm on the smaller half only.
If m < target, then:
Recursively call this algorithm on the larger half only.
Examples –
Binary Search
Suppose a is a sorted array of size n

Binary_search(array a, number target)

m ← the middle element of a. If m = target, then: Report “FOUND”

and terminate the algorithm. Else if m is the only element of a,
then: Report “NOT FOUND” and terminate the algorithm. Else: Split
the array at m into two equal halves, a smaller half and a larger
half. If m > target, then: Recursively call this algorithm on the
smaller half only. If m < target, then: Recursively call this
algorithm on the larger half only.

Please try to not do this!

Multiplication -
Russian Peasant Method
▪ Compute 13 × 7 = 91
x y Add
13 7
Multiplication -
Russian Peasant Method
▪ Compute 13 × 7 = 91
x y Add
13 7 7
6 14
Multiplication -
Russian Peasant Method
▪ Compute 13 × 7 = 91
x y Add
13 7 7
6 14 -
3 28
Multiplication -
Russian Peasant Method
Is x odd?
▪ Compute 13 × 7 = 91
x y Add
13 7 7 Do Do
6 14 - something something
3 28 28
1 56
Is x>1?

Repeat until x reaches 1

Add up and
output product
Multiplication -
Russian Peasant Method
Is x odd?
Russian_Peasant_1(x,y)
p ← 0
while x>1 do
if x is odd then Do Do
p ← p+y something something
x ← x/2
y ← 2y
else
x ← x/2 Is x>1?
y ← 2y
end while
p ← p + y Add up and
print p output product
Multiplication -
Russian Peasant Method
Russian_Peasant_1(x,y) Russian_Peasant_2(x,y)
p ← 0 p ← 0
while x>1 do while x>0 do
if x is odd then if x is odd then
p ← p+y p ← p+y
x ← x/2 x ← x/2
y ← 2y y ← 2y
else end while
x ← x/2 print p
y ← 2y
end while
p ← p + y
print p
Multiplication -
Russian Peasant Method
▪ Compute 13 × 7 = 91 Russian_Peasant_2(x,y)
p ← 0
iteration x y p while x>0 do
initialize 13 7 0 if x is odd then
p ← p+y
After 1st 6 14 0+7 = 7 x ← x/2
After 2nd 3 28 7 y ← 2y
After 3rd 1 56 7+28 = 35 end while
print p
After 4th 0 108 35+56 = 91
Russian Peasant Method –
Time Complexity
▪ Compute 13 × 7 = 91 Russian_Peasant_2(x,y)
p ← 0
iteration x y p while x>0 do
initialize 13 7 0 if x is odd then
p ← p+y
After 1st 6 14 0+7 = 7 x ← x/2
After 2nd 3 28 7 y ← 2y
After 3rd 1 56 7+28 = 35 end while
print p
After 4th 0 108 35+56 = 91

Running Time. Let 𝑛 be number of digits of 𝑥 and 𝑦, i.e. input size

is 𝑂 𝑛 . Then we have running time
𝑇 𝑛 = #iteration × time for each iteration
= #iteration × 𝑂 𝑛 = 𝑛 × 𝑂 𝑛 = 𝑂 𝑛2 .
Russian Peasant Method –
Proof of Correctness
▪ Compute 13 × 7 = 91 Russian_Peasant_2(x,y)
p ← 0
iteration x y p while x>0 do
initialize 13 7 0 if x is odd then
p ← p+y
After 1st 6 14 0+7 = 7 x ← x/2
After 2nd 3 28 7 y ← 2y
After 3rd 1 56 7+28 = 35 end while
print p
After 4th 0 108 35+56 = 91

Observe: 13 × 7 = 6 × 14 + 7 = 3 × 28 + 7 = 1 × 56 + 35 = 91
Claim: Let 𝑥𝑖 be value stored in x in 𝑖-th iteration. For every 𝑖-th
iteration, 𝑥𝑖 × 𝑦𝑖 + 𝑝𝑖 = 𝑥 × 𝑦
Russian Peasant Method –
Proof of Correctness Russian_Peasant_2(x,y)
p ← 0
while x>0 do
if x is odd then
Claim: p ← p+y
For every 𝑖-th iteration, 𝑥𝑖 × 𝑦𝑖 + 𝑝𝑖 = 𝑥 × 𝑦 x ← x/2
y ← 2y
Mathematical Induction: end while
print p
▪ Base Step: iteration x y p
(Show claim is true for i=0) initialize 13 7 0

𝑥0 × 𝑦0 + 𝑝0 = 𝑥 × 𝑦 After 1st 6 14 0+7 = 7

After 2nd 3 28 7

▪ Hypothesis: After 3rd 1 56 7+28 = 35

After 4th 0 108 35+56 = 91
(Show claim is true for some i=k-1)
Suppose that 𝑥𝑘−1 × 𝑦𝑘−1 + 𝑝𝑘−1 = 𝑥 × 𝑦 for some 𝑘
Russian Peasant Method –
Proof of Correctness Russian_Peasant_2(x,y)
p ← 0
while x>0 do
Claim: if x is odd then
p ← p+y
For every 𝑖-th iteration, 𝑥𝑖 × 𝑦𝑖 + 𝑝𝑖 = 𝑥 × 𝑦 x ← x/2
y ← 2y
▪ Induction Step: end while
(Show claim is true for i=k) print p

Case 1: 𝑥𝑘−1 is even. iteration x y p

initialize 13 7 0
𝑝𝑘 = 𝑝𝑘−1 After 1st 6 14 0+7 = 7
𝑥𝑘−1
Then ൞ 𝑥𝑘 = 2 After 2nd 3 28 7
After 3rd 1 56 7+28 = 35
𝑦𝑘 = 2𝑦𝑘−1
After 4th 0 108 35+56 = 91
𝑥
𝑥𝑘 × 𝑦𝑘 + 𝑝𝑘 = 𝑘−1 × 2𝑦𝑘−1 + 𝑝𝑘−1
2
= 𝑥𝑘−1 × 𝑦𝑘−1 + 𝑝𝑘−1 = 𝑥 × 𝑦
Russian Peasant Method –
Proof of Correctness Russian_Peasant_2(x,y)
p ← 0
while x>0 do
Claim: if x is odd then
p ← p+y
For every 𝑖-th iteration, 𝑥𝑖 × 𝑦𝑖 + 𝑝𝑖 = 𝑥 × 𝑦 x ← x/2
y ← 2y
▪ Induction Step: end while
(Show claim is true for k) print p

Case 2: 𝑥𝑘−1 is odd. iteration x y p

initialize 13 7 0
𝑝𝑘 = 𝑝𝑘−1 + 𝑦 After 1st 6 14 0+7 = 7
𝑥 −1
Then ൞ 𝑥𝑘 = 𝑘−1
2
After 2nd 3 28 7
After 3rd 1 56 7+28 = 35
𝑦𝑘 = 2𝑦𝑘−1 After 4th 0 108 35+56 = 91
𝑥 −1
𝑥𝑘 × 𝑦𝑘 + 𝑝𝑘 = 𝑘−1 × 2𝑦𝑘−1 + 𝑝𝑘−1 + 𝑦
2
= 𝑥𝑘−1 × 𝑦𝑘−1 + 𝑝𝑘−1 = 𝑥 × 𝑦