Complexity of

Algorithms

Le Thanh Sach

Chapter 2
Complexity of Algorithms Algorithm
Efficiency

Big-O notation
Data Structures and Algorithms Problems and
common
complexities

P and NP
Problems
Le Thanh Sach
Faculty of Computer Science and Engineering
University of Technology, VNU-HCM

2.1
 Complexity of
Outcomes Algorithms

Le Thanh Sach

• L.O.1.1 - Define concept “computational complexity”

and its sepcial cases, best, average, and worst.
• L.O.1.2 - Analyze algorithms and use Big-O notation to
Algorithm
characterize the computational complexity of algorithms Efficiency

composed by using the following control structures: Big-O notation

sequence, branching, and iteration (not recursion). Problems and

common
• L.O.1.3 - List, give examples, and compare complexity complexities

P and NP
classes, for examples, constant, linear, etc. Problems

• L.O.1.4 - Be aware of the trade-off between space and

time in solutions.
• L.O.1.5 - Describe strategies in algorithm design and
problem solving.

2.2
 Complexity of
Contents Algorithms

Le Thanh Sach

1 Algorithm Efficiency

Algorithm
Efficiency

2 Big-O notation Big-O notation

Problems and
common
complexities

3 Problems and common complexities P and NP

Problems

4 P and NP Problems

2.3
 Complexity of
Algorithms

Le Thanh Sach

Algorithm
Efficiency

Algorithm Efficiency Big-O notation

Problems and
common
complexities

P and NP
Problems

2.4
 Complexity of
Algorithm Efficiency Algorithms

Le Thanh Sach

• A problem often has many algorithms.

• Comparing two different algorithms Algorithm

Efficiency

⇒ Computational complexity: Big-O notation

Problems and
common
measure of the difficulty degree (time complexities

P and NP
and/or space) of an algorithm. Problems

• How fast an algorithm is?

• How much memory does it cost?

2.5
 Complexity of
Algorithm Efficiency Algorithms

Le Thanh Sach

General format
Algorithm
Efficiency
efficiency = f(n) Big-O notation

n is the size of a problem (the key Problems and

common
complexities

number that determines the size of input P and NP

Problems

data)

2.6
 Complexity of
Linear Loops Algorithms

Le Thanh Sach

for ( i = 0; i < 1000; i ++)

application code

The number of times the body of the loop is replicated is

1000. Algorithm
Efficiency

Big-O notation
f(n) = n
Problems and
common
complexities

P and NP
Problems

for ( i = 0; i < 1000; i += 2)

application code

The number of times the body of the loop is replicated is

500.

f(n) = n/2
2.7
 Complexity of
Linear Loops Algorithms

time f (n) = n Le Thanh Sach

Algorithm
Efficiency

Big-O notation

Problems and
common
f (n) = n/2 complexities

P and NP
Problems

n 2.8
 Complexity of
Logarithmic Loops Algorithms

Le Thanh Sach

Multiply loops

i = 1
while ( i <= n )
application code
i = i x 2 Algorithm
Efficiency

Big-O notation

Divide loops Problems and

common
complexities
i = n P and NP
while ( i >= 1) Problems

application code
i = i / 2

The number of times the body of the loop is replicated is

f(n) = log2 n

2.9
 Complexity of
Logarithmic Loops Algorithms
time Le Thanh Sach

Algorithm
Efficiency

Big-O notation

Problems and
common
complexities

P and NP
Problems

f (n) = log2 n

n 2.10
 Complexity of
Nested Loops Algorithms

Le Thanh Sach

Iterations = Outer loop iterations × Inner loop iterations

Example
Algorithm
Efficiency
i = 1
Big-O notation
while ( i <= n )
Problems and
j = 1 common
while ( j <= n ) complexities

application code P and NP

Problems
j = j * 2
i = i + 1

The number of times the body of the loop is replicated is

f (n) = n log2 n

2.11
 Complexity of
Nested Loops Algorithms
time f (n) = n log2 n Le Thanh Sach

Algorithm
Efficiency

Big-O notation

Problems and
common
complexities

P and NP
Problems

n 2.12
 Complexity of
Quadratic Loops Algorithms

Le Thanh Sach

Example

i = 1
while ( i <= n ) Algorithm
Efficiency
j = 1
Big-O notation
while ( j <= n )
application code Problems and
common
j = j + 1 complexities
i = i + 1 P and NP
Problems

The number of times the body of the loop is replicated is

f (n) = n2

2.13
 Complexity of
Dependent Quadratic Loops Algorithms

Le Thanh Sach

Example

i = 1
while ( i <= n ) Algorithm
Efficiency
j = 1
Big-O notation
while ( j <= i )
application code Problems and
common
j = j + 1 complexities
i = i + 1 P and NP
Problems

The number of times the body of the loop is replicated is

1 + 2 + . . . + n = n(n + 1)/2

2.14
 Complexity of
Quadratic Loops Algorithms
time f (n) = n2 Le Thanh Sach

Algorithm
Efficiency

Big-O notation

Problems and
common
complexities

P and NP
Problems

n 2.15
 Complexity of
Asymptotic Complexity Algorithms

Le Thanh Sach

• Algorithm efficiency is considered

with only big problem sizes.
Algorithm
Efficiency
• We are not concerned with an exact Big-O notation

measurement of an algorithm’s Problems and

common
complexities

efficiency. P and NP
Problems

• Terms that do not substantially

change the function’s magnitude are
eliminated.

2.16
 Complexity of
Algorithms

Le Thanh Sach

Algorithm
Efficiency

Big-O notation Big-O notation

Problems and
common
complexities

P and NP
Problems

2.17
 Complexity of
Big-O notation Algorithms

Le Thanh Sach

Example
f (n) = c.n ⇒ f (n) = O(n)
f (n) = n(n + 1)/2 = n2 /2 + n/2 ⇒ f (n) = O(n2 )
Algorithm
Efficiency

Big-O notation
• Set the coefficient of the term to one. Problems and
common
complexities
• Keep the largest term and discard the P and NP
Problems
others.
Some example of Big-O:
log2 n n n log2 n n2 ... nk ... 2n n!

2.18
 Complexity of
Standard Measures of Efficiency Algorithms

Le Thanh Sach

Efficiency Big-O Iterations Est. Time

logarithmic O(log2 n) 14 microseconds
linear O(n) 10 000 0.1 seconds
Algorithm
linear log O(n log2 n) 140 000 2 seconds Efficiency

quadratic O(n2 ) 100002 15-20 min. Big-O notation

polynomial O(nk ) 10000k hours Problems and

common
exponential O(2n ) 210000 intractable complexities

P and NP
factorial O(n!) 10000! intractable Problems

Assume instruction speed of 1 microsecond and 10

instructions in loop.
n = 10000

2.19
 Complexity of
Standard Measures of Efficiency Algorithms

time n2 n log n Le Thanh Sach

2
n

Algorithm
Efficiency

Big-O notation

Problems and
common
complexities

P and NP
Problems

log2 n

n 2.20
 Complexity of
Big-O Analysis Examples Algorithms

Le Thanh Sach

Algorithm addMatrix(val matrix1<matrix>, val

matrix2<matrix>, val size<integer>, ref matrix3<matrix>)
Add matrix1 to matrix2 and place results in matrix3
Pre: matrix1 and matrix2 have data
size is number of columns and rows in matrix Algorithm
Efficiency
Post: matrices added - result in matrix3 Big-O notation
r=1 Problems and
common
while r <= size do complexities
c=1 P and NP
while c <= size do Problems

matrix3[r, c] = matrix1[r, c] + matrix2[r, c]

c=c+1
end
r=r+1
end
return matrix3
End addMatrix
2.21
 Complexity of
Big-O Analysis Examples Algorithms

Le Thanh Sach

Algorithm
Efficiency

Nested linear loop: Big-O notation

Problems and
f (size) = O(size2) common
complexities

P and NP
Problems

2.22
 Complexity of
Time Costing Operations Algorithms

Le Thanh Sach

• The most time consuming: data Algorithm

Efficiency
movement to/from memory/storage. Big-O notation

Problems and
common
• Operations under consideration: complexities

P and NP
• Comparisons Problems
• Arithmetic operations
• Assignments

2.23
 Complexity of
Algorithms

Le Thanh Sach

Problems and common

Algorithm
Efficiency

Big-O notation

complexities Problems and

common
complexities

P and NP
Problems

2.24
 Complexity of
Binary search Algorithms

Le Thanh Sach

Recurrence Equation (Phương trình hồi quy)

An equation or inequality that describes a Algorithm

Efficiency

function in terms of its value on smaller input. Big-O notation

Problems and
common
complexities

P and NP
Problems

1 2 3 5 8 13 21 34 55 89
T (n) = 1 + T (n/2) ⇒ T (n) = O(log2 n)

2.25
 Complexity of
Binary search Algorithms

Le Thanh Sach

• Best case: when the number of steps

is smallest. T (n) = O(1) Algorithm
Efficiency

Big-O notation
• Worst case: when the number of steps Problems and
common

is largest. T (n) = O(log2 n) complexities

P and NP
Problems
• Average case: in between.
T (n) = O(log2 n)

2.26
 Complexity of
Sequential search Algorithms

Le Thanh Sach

8 5 21 2 1 13 4 34 7 18

Algorithm
Efficiency

• Best case: T (n) = O(1) Big-O notation

Problems and
• Worst case: T (n) = O(n) common
complexities

Average case: T (n) = ni=1 [Link]

P P and NP
• Problems

pi : probability for theP

target being at a[i]
pi = 1/n ⇒ T (n) = ( ni=1 i)/n =
O(n(n + 1)/2n) = O(n)

2.27
 Complexity of
Quick sort Algorithms

Le Thanh Sach

19 8 3 15 28 10 22 4 12 83

Algorithm
Efficiency
Recurrence Equation
Big-O notation

T (n) = O(n) + 2T (n/2) Problems and

common
complexities

P and NP
Problems

• Best case: T (n) = O(n log2 n)

• Worst case: T (n) = O(n2 )
• Average case: T (n) = O(n log2 n)

2.28
 Complexity of
Algorithms

Le Thanh Sach

Algorithm
Efficiency

P and NP Problems Big-O notation

Problems and
common
complexities

P and NP
Problems

2.29
 Complexity of
P and NP Problems Algorithms

Le Thanh Sach

• P: Polynomial (can be solved in

polynomial time on a deterministic Algorithm
Efficiency

machine). Big-O notation

Problems and
common
complexities

• NP: Nondeterministic Polynomial P and NP

Problems

(can be solved in polynomial time on

a nondeterministic machine).

2.30
 Complexity of
P and NP Problems Algorithms

Le Thanh Sach
Travelling Salesman Problem:
A salesman has a list of cities, each of which he must visit
exactly once. There are direct roads between each pair of
cities on the list.
Find the route the salesman should follow for the shortest Algorithm
Efficiency
possible round trip that both starts and finishes at any one
Big-O notation
of the cities.
Problems and
common
complexities
8
b c P and NP
Problems
7
9 5
15
a d
6 9
8
11
e f

2.31
 Complexity of
P and NP Problems Algorithms

Le Thanh Sach

Travelling Salesman Problem:

Deterministic machine: f (n) = n(n − 1)(n − 2) . . . 1 = O(n!)
⇒ NP problem
Algorithm
Efficiency

8 Big-O notation
b c Problems and
7 common
complexities
9 5 P and NP
15 Problems
a d
6 9
8
11
e f

2.32
 Complexity of
P and NP Problems Algorithms

Le Thanh Sach

NP-complete: NP and every other problem in NP is

polynomially reducible to it.

Algorithm
Efficiency
P Big-O notation

Problems and
common
NP complexities

P and NP
Problems
NP-complete

P = NP?

2.33