Data Structure and Algorithms [CO2003]

Chapter 2 - Algorithm Complexity

Lecturer: Vuong Ba Thinh

Contact: [email protected]

Faculty of Computer Science and Engineering

Hochiminh city University of Technology
Contents

1. Algorithm Eciency

2. Big-O notation

3. Problems and common complexities

4. P and NP Problems

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 1 / 28
Outcomes

ˆ L.O.1.1 - Dene concept computational complexity and its special

cases, best, average, and worst.

ˆ L.O.1.2 - Analyze algorithms and use Big-O notation to

characterize the computational complexity of algorithms composed

by using the following control structures: sequence, branching, and

iteration (not recursion).

ˆ L.O.1.3 - List, give examples, and compare complexity classes, for

examples, constant, linear, etc.

ˆ L.O.1.4 - Be aware of the trade-o between space and time in

solutions.

ˆ L.O.1.5 - Describe strategies in algorithm design and problem

solving.

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 2 / 28
Algorithm Eciency
Algorithm Eciency

ˆ A problem often has many algorithms.

ˆ Comparing two dierent algorithms ⇒ Computational complexity:

measure of the diculty degree (time and/or space) of an algorithm.

ˆ How fast an algorithm is?

ˆ How much memory does it cost?

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 3 / 28
Algorithm Eciency

General format
eciency = f(n)
n is the size of a problem (the key number that determines the size of

input data)

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 4 / 28
Linear Loops

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

// a p p l i c a t i o n code

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

f(n) = n

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

// a p p l i c a t i o n code

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

f(n) = n/2
Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 5 / 28
Linear Loops

time f (n) = n

f (n) = n/2

n
Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 6 / 28
Logarithmic Loops
Multiply loops
i = 1
while ( i <= n )
// a p p l i c a t i o n code
i = i x 2
end while

Divide loops
i = n
while ( i >= 1 )
// a p p l i c a t i o n code
i = i / 2
end while

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

f(n) = log 2 n

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 7 / 28
Logarithmic Loops

time

f (n) = log2 n

n
Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 8 / 28
Nested Loops

Iterations = Outer loop iterations × Inner loop iterations

Example
i = 1
while ( i <= n )
j = 1
while ( j <= n )
// a p p l i c a t i o n code
j = j * 2
end while

i = i + 1
end while

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

f (n) = n log2 n

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 9 / 28
Nested Loops

time f (n) = n log2 n

n
Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 10 / 28
Quadratic Loops

Example
i = 1
while ( i <= n )
j = 1
while ( j <= n )
// a p p l i c a t i o n code
j = j + 1
end while

i = i + 1
end while

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

f (n) = n2

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 11 / 28
Dependent Quadratic Loops

Example
i = 1
while ( i <= n )
j = 1
while ( j <= i )
// a p p l i c a t i o n code
j = j + 1
end while

i = i + 1
end while

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

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

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 12 / 28
Quadratic Loops

time f (n) = n2

n
Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 13 / 28
Asymptotic Complexity

ˆ Algorithm eciency is considered with only big problem sizes.

ˆ We are not concerned with an exact measurement of an algorithm's

eciency.

ˆ Terms that do not substantially change the function's magnitude are

eliminated.

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 14 / 28
Big-O notation
Big-O notation

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

ˆ Set the coecient of the term to one.

ˆ Keep the largest term and discard the others.

Some example of Big-O:

log2 n, n, n log2 n, n2 , ... nk ... 2n , n!

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 15 / 28
Standard Measures of Eciency

Eciency Big-O Iterations Est. Time

logarithmic O(log2 n) 14 microseconds

linear O(n) 10 000 0.1 seconds

linear log O(n log2 n) 140 000 2 seconds

2 2
quadratic O(n ) 10000 15-20 min.
k
polynomial O(n ) 10000k hours
n
exponential O(2 ) 210000 intractable

factorial O(n!) 10000! intractable

Assume instruction speed of 1 microsecond and 10 instructions in loop.

n = 10000

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 16 / 28
Standard Measures of Eciency

time n2 n log n
2
n

log2 n

n
Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 17 / 28
Big-O Analysis Examples

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
Post: matrices added - result in matrix3
r = 1
while r <= size do
c = 1
while c <= size do
matrix3[r, c] = matrix1[r, c] + matrix2[r, c]
c = c + 1
end

r = r + 1
end

return matrix3
End addMatrix

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 18 / 28
Big-O Analysis Examples

Nested linear loop:

D
Y
f (S) = O( Si )
i=1

f (size) = O(size2 )

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 19 / 28
Time Costing Operations

ˆ The most time consuming: data movement to/from

memory/storage.

ˆ Operations under consideration:

ˆ Comparisons

ˆ Arithmetic operations

ˆ Assignments

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 20 / 28
Problems and common
complexities
Binary search

Recurrence Equation
An equation or inequality that describes a function in terms of its value

on smaller input.

1 2 3 5 8 13 21 34 55 89

T (n) = 1 + T (n/2) ⇒ T (n) = O(log2 n)

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 21 / 28
Binary search

ˆ Best case: when the number of steps is smallest. T (n) = O(1)

ˆ Worst case: when the number of steps is largest. T (n) = O(log2 n)
ˆ Average case: in between. T (n) = O(log2 n)

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 22 / 28
Sequential search

8 5 21 2 1 13 4 34 7 18

ˆ Best case: T (n) = O(1)

ˆ Worst case: T (n) = O(n)
Pn
ˆ Average case: T (n) = i=1 i.pi
pi : probability for the target being at a[i]
Pn
pi = 1/n ⇒ T (n) = ( i=1 i)/n = O(n(n + 1)/2n) = O(n)

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 23 / 28
Quick sort

19 8 3 15 28 10 22 4 12 83

Recurrence Equation
T (n) = O(n) + 2T (n/2)

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

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

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 24 / 28
P and NP Problems
P and NP Problems

ˆ P: Polynomial (can be solved in polynomial time on a deterministic

machine).

ˆ NP: Nondeterministic Polynomial (can be solved in polynomial time

on a nondeterministic machine).

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 25 / 28
P and NP Problems

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 possible round

trip that both starts and nishes at any one of the cities.

8
b c
7
9 5
15
a d
6 9
8
11
e f

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 26 / 28
P and NP Problems

Travelling Salesman Problem:

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

8
b c
7
9 5
15
a d
6 9
8
11
e f

Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 27 / 28
P and NP Problems

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

reducible to it.

NP

NP-complete

P = NP?
Lecturer: Vuong Ba Thinh Contact: [email protected] Data Structure and Algorithms [CO2003] 28 / 28