COMP90038
Algorithms and Complexity
Lecture 3: Growth Rate and Algorithm Efficiency (with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Update
Compulsory Quizzes (first one closes Tuesday Week 3)
Tutorials start this week
Background knowledge catch-up tutorials:
Weeks 2 and 3
• • •
•
• •
Discussion Board
Thursday 1-2pm and 2:15-3:15pm
Consultation Hours
•
Alice Hoy, Room 101
Algorithm Efficiency
Two algorithms for computing gcd:
Why is one more efficient than the other?
What does “efficient” even mean?
How can we talk about these things precisely?
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Linear Search Example
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,7)
(returns 4)
A: Y A[j]
x: 7
n: 7
j: 40123
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Linear Search Example
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
How many times does the loop run to find 7?
5.
How many times does the loop run to find 99? 7.
(the length of the array)
return -1
How many times does the loop run to find 6? 1.
5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Assessing Algorithm “Efficiency”
Resources consumed: time and space
We want to assess efficiency as a function of input
Mathematical vs empirical assessment Average case vs worst case
•
•
size
• •
Knowledge about input peculiarities may affect the
•
choice of algorithm
The right choice of algorithm may also depend on
•
the programming language used for implementation
7
Running Time Dependencies
There are many things that a program’s running time
•
depends on:
1.Complexity of the algorithms used
2.Input to the program
3.Underlying machine, including memory architecture 4.Language/compiler/operating system
Since we want to compare algorithms we ignore (3) and Use a natural number n to quantify (2)—size of the input
•
(4); just consider units of time
• •
Express (1) as a function of n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Linear Search Example
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
n = the length of the array How should we quantify the cost to run this algorithm?
roughly, number of times the loop runs
(later in this lecture we will be more precise)
return -1
How should we measure the size, n,
of the input to this algorithm?
Linear Search Example
9
(since the loop runs n times in that case) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
return -1
What is the worst case input? an array that doesn’t contain the
item, x, we are searching for Worst case time complexity: n
Linear Search Example
10
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
return -1
What is the best case input? an array that has the item, x,
we are searching for in the first position
Best case time complexity: 1 (since the loop runs once in that case)
11
Estimating Time Consumption
Number of loop iterations is not a good estimate of
•
running time.
Better is to identify the algorithm’s basic operation
•
and how many times it is performed
•
If c is the cost of a basic operation and g(n) is the number of times the operation is performed for input size n,
then running time t(n) ≈ c ⋅ g(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Linear Search Example
12
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
return -1
What is the basic operation here? the comparison A[j] = x
Rule of thumb: the most expensive operation executed each time in the inner-most loop of the program
Examples:
Input Size and Basic Operation
Problem Size Measure
Basic Operation
Key comparison
Search in a list
of n items
n
Multiply two Matrix size
matrices of floats (rows x columns)
Float multiplication
Compute an log n
Float multiplication
Graph problem Number of nodes Visiting a node and edges
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Best, Average and Worst Case
The running time t(n) may well depend on more than just n Worse case: analysis makes the most pessimistic
assumptions about the input
Best case: analysis makes the most optimistic assumptions about the input
Average case: analysis aims to find the expected running time across all possible input of size n
(Note: not an average of the worst and best cases)
•
•
•
•
Amortised analysis takes context of running an algorithm
•
into account, calculates cost spread over many runs. Used
for “self-organising” data structures that adapt to their usage
Large Input is what Matters
Small input does not properly stress an algorithm
for small values of m and n, their cost is similar
•
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Only as we let m and n grow large do we witness
•
(big) differences in performance.
16
Guessing Game Example
Guess which number I am thinking of, between 1 and n (inclusive). I will tell you if it is higher or lower than each guess.
•
1
5051 75 100 Wrong. My number is lhoiwgheer rththaann750. .
We are halving the search space each time. Basic operation: guessing a number.
(Worse case) complexity: log n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
The Tyranny of Growth Rate
3 101 3 ·101 102 103 103 4 · 106
7 102 7 · 102 104 106 1030 9 · 10157
10 103 1 · 104 106 109 - -
1030 is 1,000 times the number of nano-seconds since the Big Bang.
At a rate of a trillion (1012) operations per second, executing 2100
operations would take a computer in the order of 1010 years.
That is more than the estimated age of the Earth
n log2 n n n log2 n n2 n3 2n n!
101 102 103
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
The Tyranny of Growth Rate
18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
19
Functions Often Met in
Algorithm Classification
•
1: Running time independent of input
log n: typical for “divide an conquer” solutions, for example
•
lookup in a balanced search tree
•
•
Linear (n): When each input must be processed once
n log n: Each input element processed once and processing involves other elements too, for example, sorting.
n2, n3: Quadratic, cubic. Processing all pairs (triples) of
•
elements.
•
2n: Exponential. Processing all subsets of elements. Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
20
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Asymptotic Analysis
•
•
•
We are interested in the growth rate of functions Ignore constant factors
Ignore small input sizes
21
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Asymptotics
f(n) ≺ g(n) iff lim f(n) = 0
•
• •
•
n→∞
That is, g approaches infinity faster than f
g(n) 1≺logn≺nε ≺nc ≺nlogn ≺cn ≺nn
where 0 < ε < 1 < c
In asymptotic analysis, think big!
e.g., log n ≺ n0.0001, even though for n = 10100,
•
100 > 1.023.
•
Try it for n = 101000000
22
Big-Oh Notation
•
•
O(g(n)) denotes the set of functions that grow no Formal definition: We write
•
faster than g, asymptotically.
t(n) ∈ O(g(n))
when, for some c and n0
n > n0 ⇒ t(n) < c ·g(n)
For example: 1 + 2 + ... + n ∈ O(n2)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Big-Oh: What t(n) ∈ O(g(n)) Means
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
24
Big-Oh Pitfalls
Levitin’s notation t(n) ∈ O(g(n)) is meaningful, but Other authors use t(n) = O(g(n)) for the same thing.
As O provides an upper bound, it is correct to say both 3n ∈ O(n2) and 3n ∈ O(n) (so you can see why
using ‘=’ is confusing); the latter, 3n ∈ O(n), is of course more precise and useful.
Note that c and n0 may be large.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
not standard.
• •
•
25
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Big-Omega and Big-Theta
Big Omega: Ω(g(n)) denotes the set of functions for lower bounds.
•
that grow no slower than g, asymptotically, so Ω is
•
•
t(n) ∈ Θ(g(n)) iff t(n) ∈ O(g(n)) and t(n) ∈ Ω(g(n)).
t(n) ∈ Ω(g(n)) iff n >n0 ⇒ t(n) > c ·g(n),
Big Theta: Θ is for exact order of growth.
•
for some n0 and c.
Big-Omega: What t(n) ∈ Ω(g(n)) Means
26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Big-Theta: What t(n) ∈ Θ(g(n)) Means
27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
28
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Establishing Growth Rate
We can use the definition of O directly.
•
t(n) ∈ O(g(n)) iff: n > n0 ⇒ t(n) < c ·g(n) Exercise: use this to show that
•
1 + 2 + ... + n ∈ O(n2)
Also show that:
•
17n2 + 85n + 1024 ∈ O(n2)
1 + 2 + ... + n ∈ O(n2)
Find some c and n0 such that, for all n > n0
1 + 2 + … + n < c · n2 1 + 2 + ...+ n
n(n+1) 2
n2 + n 2
n2 + n n2 + n2
Choosen0 =1,c=2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
=
= <
< =
(for n > 0) (for n > 1)
29
2n2
30
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
17n2 + 85n + 1024 ∈ O(n2)
Find some c and n0 such that, for all n > n0
17n2 + 85n + 1024 < c · n2 Guess c = 18 Need to prove:
17n2 + 85n + 1024 < 18n2 i.e. 85n + 1024 < n2
Guess n0 = 1024 Check if: 85n0+ 1024 < n02 85·1024 + 1024 < 1024·1024
i.e. 86·1024 < 1024·1024 Clearly true.
Choose c = 18, n0 = 1024
31
17n2 + 85n + 1024 < c · n2 Alternative: Let c = 17 + 85 + 1024
17n2 + 85n + 1024
< 17n2 + 85n2 + 1024n2 (for n > 1)
= (17 + 85 + 1024)n2 Choosec=17+85+1024,n0 =1
Of course, this works for any polynomial. Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
17n2 + 85n + 1024 ∈ O(n2)
Find some c and n0 such that, for all n > n0