Data Structure and Algorithms [CO2003]

Chapter 2 - Algorithm Complexity

Lecturer: Duc Dung Nguyen, PhD.

Contact: [email protected]

Faculty of Computer Science and Engineering

Hochiminh city University of Technology
 Contents

1. Algorithm Efficiency

2. Big-O notation

3. Problems and common complexities

4. P and NP Problems

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 1 / 28
 Outcomes

• L.O.1.1 - Define 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-off between space and time in solutions.
• L.O.1.5 - Describe strategies in algorithm design and problem solving.

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 2 / 28
Algorithm Efficiency
 Algorithm Efficiency

• A problem often has many algorithms.

• Comparing two different algorithms ⇒ Computational complexity: measure of the
difficulty degree (time and/or space) of an algorithm.
• How fast an algorithm is?
• How much memory does it cost?

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 3 / 28
 Algorithm Efficiency

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

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 4 / 28
 Linear Loops

f o r ( i = 0 ; i < 1 0 0 0 ; i ++)
// a p p l i c a t i o n c o d e

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

f (n) = n

f o r ( i = 0 ; i < 1 0 0 0 ; i += 2 )
// a p p l i c a t i o n c o d e

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

f (n) = n/2
Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 5 / 28
 Linear Loops

time f (n) = n

f (n) = n/2

n
Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 6 / 28
 Logarithmic Loops

Multiply loops
i = 1
w h i l e ( i <= n )
// a p p l i c a t i o n c o d e
i = i x 2
end w h i l e

Divide loops
i = n
w h i l e ( i >= 1 )
// a p p l i c a t i o n c o d e
i = i / 2
end w h i l e

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

f (n) = log2 n
Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 7 / 28
 Logarithmic Loops

time

f (n) = log2 n

n
Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 8 / 28
 Nested Loops

Iterations = Outer loop iterations × Inner loop iterations

Example
i = 1
w h i l e ( i <= n )
j = 1
w h i l e ( j <= n )
// a p p l i c a t i o n c o d e
j = j ∗ 2
end w h i l e
i = i + 1
end w h i l e

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

f (n) = n log2 n

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 9 / 28
 Nested Loops

time f (n) = n log2 n

n
Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 10 / 28
 Quadratic Loops

Example
i = 1
w h i l e ( i <= n )
j = 1
w h i l e ( j <= n )
// a p p l i c a t i o n c o d e
j = j + 1
end w h i l e
i = i + 1
end w h i l e

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

f (n) = n2

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 11 / 28
 Dependent Quadratic Loops

Example
i = 1
w h i l e ( i <= n )
j = 1
w h i l e ( j <= i )
// a p p l i c a t i o n c o d e
j = j + 1
end w h i l e
i = i + 1
end w h i l e

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

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

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 12 / 28
 Quadratic Loops

time f (n) = n2

n
Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 13 / 28
 Asymptotic Complexity

• Algorithm efficiency is considered with only big problem sizes.

• We are not concerned with an exact measurement of an algorithm’s efficiency.
• Terms that do not substantially change the function’s magnitude are eliminated.

Lecturer: Duc Dung Nguyen, PhD. 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 coefficient 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: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 15 / 28
 Standard Measures of Efficiency

Efficiency 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
quadratic O(n2 ) 100002 15-20 min.
polynomial O(nk ) 10000k hours
exponential O(2n ) 210000 intractable
factorial O(n!) 10000! intractable

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

n = 10000

Lecturer: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 16 / 28
 Standard Measures of Efficiency

time n2 n log n
2
n

log2 n

n
Lecturer: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 18 / 28
 Big-O Analysis Examples

Nested linear loop:

f (size) = O(size2 )

Lecturer: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. 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]
n
X
pi = 1/n → T (n) = ( i)/n = O(n(n + 1)/2n) = O(n)
i=1

Lecturer: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. 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 finishes at any one of the cities.

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

Lecturer: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. 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: Duc Dung Nguyen, PhD. Contact: [email protected] Data Structure and Algorithms [CO2003] 28 / 28