Asymptotic Analysis of Algorithms
David Weir (U of Sussex) Program Analysis Term 1, 2015 32 / 606
Analysing Algorithm Efficiency
Things we might want to know:
How efficient is a given algorithm?
What sized problems can be solved within a reasonable time?
Is some new algorithm really more efficient that the existing one? Which of two possible algorithms is best for my particular use?
We’ll look at ways to answer questions like these
David Weir (U of Sussex) Program Analysis Term 1, 2015 33 / 606
Experimental Study
Measuring running time of an algorithm through experimentation
Implement algorithm
Choose appropriate inputs
Run program on all inputs
Plot results
Determine rate at which time increases as input grows
David Weir (U of Sussex) Program Analysis Term 1, 2015 34 / 606
Experimental Study
Can have signicant advantages:
Can give very realistic impression of actual time
Can be useful when comparing two candidate algorithms
Subtle differences in running time may emerge
Useful when software, hardware and possible inputs can be established
David Weir (U of Sussex) Program Analysis Term 1, 2015 35 / 606
Experimental Study (cont.)
Variety of potential problems:
Can be time-consuming to implement algorithms effectively
Can be time-consuming to run (slow) algorithm on (large) inputs
May not have good understanding of the context in which algorithm will be deployed
◮ software used for implementation
◮ hardware on which it will run
◮ range of inputs on which it will run
Comparing algorithms requires comparable implementations
David Weir (U of Sussex) Program Analysis Term 1, 2015 36 / 606
Asymptotic Analysis
Look at how running time increases as input size grows
A rough classification of the rate of growth Concerned with the (very) long term growth rate
Running time as a function
Problem size is n
Running time of algorithm referred to as t(n)
t(n) is the number of steps that an input of size n takes
David Weir (U of Sussex) Program Analysis Term 1, 2015 37 / 606
Asymptotic Analysis (cont.)
Measure running time in terms of number of “steps”:
lines of pseudocode lines of Java
lines of assembly code
Size of step doesn’t matter when performing asymptotic analysis
David Weir (U of Sussex) Program Analysis Term 1, 2015 38 / 606
Asymptotic Bounds
Asymptotic analysis of efficiency involves determining bounds
Upper bound O(.) Lower bound Ω(.) Tight bound Θ(.)
We’ll begin by considering each bound graphically
David Weir (U of Sussex) Program Analysis Term 1, 2015 39 / 606
Asymptotic Upper Bound: Example
steps
t(n)
n
Suppose this is a plot of the running time t(n) of our algorithm
David Weir (U of Sussex) Program Analysis Term 1, 2015 40 / 606
Questions for you
What is n a measure of for the following problems?
Finding a stable match
Sorting a sequence of numbers Searching a list for an given value Performing depth-first search of a graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 41 / 606
Questions for you
What is n a measure of for the following problems? Finding a stable match
The number of men
Sorting a sequence of numbers The number of numbers
Searching a list for an given value The length of the list
Performing depth-first search of a graph
The number of vertices and the number of edges
David Weir (U of Sussex) Program Analysis Term 1, 2015 41 / 606
Asymptotic Upper Bound: Example
steps
t(n)
n
Suppose this is a plot of the running time t(n) of our algorithm
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
t(n)
n
Can we find a function that will grow faster than this one?
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
t(n)
n
Let’s consider a linear function: e.g. f (n) = n
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
t(n) n
n
f(n) = n isn’t growing as fast as t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
t(n) n
n
Try adding a constant: f (n) = n + 10
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
t(n) n+10
n
f (n) = n + 10 has the same rate of growth as n
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
t(n) n+10
n
Try multiplying n by a constant f (n) = 3n + 10
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
3n+10
t(n)
n
f(n) = 3n + 10 still doesn’t grow as fast as t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
3n+10
t(n)
n
Any straight line (linear function) eventually gets overtaken by t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
3n+10
t(n)
n
Need something that curves upwards: e.g. f (n) = n2
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Asymptotic Upper Bound: Example
steps
n2
t(n)
After crossing at n0, n2 remains above t(n) David Weir (U of Sussex) Program Analysis
Term 1, 2015
42 / 606
n0
n
Asymptotic Upper Bound: Example
steps
n2
t(n)
n2 is an asymptotic upper bound for t(n) David Weir (U of Sussex) Program Analysis
Term 1, 2015
42 / 606
n0
n
Asymptotic Upper Bound: Example
steps
n2
t(n)
so we say t(n) is O(n2) David Weir (U of Sussex)
Program Analysis
Term 1, 2015
42 / 606
n0
n
Asymptotic Upper Bound: Example
steps
n2 t(n)
n
n0
Note that it doesn’t matter that n2 grows more rapidly than t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 42 / 606
Questions for you
Suppose t(n) = n2
What is the lowest value of n such that t(n) ≥ 10n + 20? Note that n must be a whole number
David Weir (U of Sussex) Program Analysis Term 1, 2015 43 / 606
Questions for you
Suppose t(n) = n2
What is the lowest value of n such that t(n) ≥ 10n + 20? Note that n must be a whole number
n = 12
David Weir (U of Sussex) Program Analysis Term 1, 2015 43 / 606
Asymptotic Upper Bound: Another Example
steps
t(n)
n
Consider another running time that grows more rapidly
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
t(n)
n
Try f (n) = n2 as a possible asymptotic upper bound
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
t(n)
n2
n
f(n) = n2 doesn’t seem to be catching up with t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
t(n)
n2
n
Tr y f ( n ) = n 2 + 1 0 David Weir (U of Sussex)
Program Analysis
Term 1, 2015
44 / 606
Asymptotic Upper Bound: Another Example
steps
t(n)
n2 + 10
n
f (n) = n2 + 10 is still not increasing at the required rate
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
t(n)
n2 + 10
n
Need something that grows faster
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
t(n)
n2 + 10
n
Try f(n) = 3n2 David Weir (U of Sussex)
Program Analysis
Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
3n2 t(n)
n
f (n) = 3n2 has adequate growth rate
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
3n2 t(n)
n0 After crossing at n0, 3n2 stays ahead
n
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
3n2 t(n)
n
3n2 is an asymptotic upper bound for t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
3n2 t(n)
n
We say t(n) is O(n2) (the constant can be dropped)
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
4n2 3n2
t(n)
n
Note that 4n2 is also an asymptotic upper bound for t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 44 / 606
Asymptotic Upper Bound: Another Example
steps
n3
4n2 3n2
t(n)
n
Even n3 counts as an asymptotic upper bound for t(n)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
44 / 606
Asymptotic Upper Bound: Another Example
steps
n3 4n2 3n2
t(n)
n
So t(n) is also O(n3) David Weir (U of Sussex)
Program Analysis
Term 1, 2015
44 / 606
Asymptotic Upper Bound
Definition of O(f (n)):
t(n) is O(f(n)) if
there are constants n0 and c > 0 such that
t(n)≤c·f(n) foralln≥n0
David Weir (U of Sussex) Program Analysis Term 1, 2015 45 / 606
Question for you
Suppose that t(n) = 3n2 + 2n + 5 Give values for n0 and c such that
t(n) ≤ c · n2 for all n ≥ n0
Give whole number values that are as low as possible
David Weir (U of Sussex) Program Analysis Term 1, 2015 46 / 606
Question for you
Suppose that t(n) = 3n2 + 2n + 5 Give values for n0 and c such that
t(n) ≤ c · n2 for all n ≥ n0
Give whole number values that are as low as possible
n0 =4andc=4
David Weir (U of Sussex) Program Analysis Term 1, 2015 46 / 606
Less Significant Terms
Consider the running time:
t(n)=14n4 +52n3logn+47n2 +3n+17
David Weir (U of Sussex) Program Analysis Term 1, 2015 47 / 606
Less Significant Terms
Consider the running time:
t(n)=14n4 +52n3logn+47n2 +3n+17
Compare this to the function
f (n) = 15 · n4
David Weir (U of Sussex) Program Analysis Term 1, 2015 47 / 606
Less Significant Terms
Consider the running time:
t(n)=14n4 +52n3logn+47n2 +3n+17
Compare this to the function
f (n) = 15 · n4
f(n) will eventually catch up with t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 47 / 606
Less Significant Terms
Consider the running time:
t(n)=14n4 +52n3logn+47n2 +3n+17
Compare this to the function
f (n) = 15 · n4
f(n) will eventually catch up with t(n)
So only consider highest order (most significant) term
David Weir (U of Sussex) Program Analysis Term 1, 2015 47 / 606
Less Significant Terms
Consider the running time:
t(n)=14n4 +52n3logn+47n2 +3n+17
Compare this to the function
f (n) = 15 · n4
f(n) will eventually catch up with t(n)
So only consider highest order (most significant) term t(n) is O(n4)
David Weir (U of Sussex) Program Analysis Term 1, 2015 47 / 606
Question for you
What is the lowest value of n where f (n) = 15 · n4 is greater than t(n)=14n4 +52n3logn+47n2 +3n+17
David Weir (U of Sussex) Program Analysis Term 1, 2015 48 / 606
Question for you
What is the lowest value of n where f (n) = 15 · n4 is greater than t(n)=14n4 +52n3logn+47n2 +3n+17
n = 106
David Weir (U of Sussex) Program Analysis Term 1, 2015 48 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4
David Weir (U of Sussex) Program Analysis Term 1, 2015 49 / 606
Ignoring Constants
Consider the running time
t(n) is O(n4)
t(n) = 100000n4
David Weir (U of Sussex) Program Analysis Term 1, 2015 49 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4 Consider the rather different running time
t(n) = 0.000001n4
t(n) is O(n4)
David Weir (U of Sussex) Program Analysis Term 1, 2015 49 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4 Consider the rather different running time
t(n) = 0.000001n4
t(n) is still O(n4)
t(n) is O(n4)
David Weir (U of Sussex) Program Analysis Term 1, 2015 49 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4 Consider the rather different running time
t(n) is O(n4)
t(n) = 0.000001n4
Lack of concern for constants is consistent with our lack of concern for
t(n) is still O(n4)
the granularity with which we measure running time
David Weir (U of Sussex) Program Analysis Term 1, 2015 49 / 606
Landmark Growth Rates
We now consider a few of the more common growth rates
David Weir (U of Sussex) Program Analysis Term 1, 2015 50 / 606
Constant Time
f(n) = 1
Expression of upper bound, written O(1)
Same as O(2), O(3), . . .
Referred to as constant time
Running time doesn’t increase with size of problem
Example: Operations on a stack (push, pop, etc)
David Weir (U of Sussex) Program Analysis Term 1, 2015 51 / 606
Linear Time
f(n) = n
Expression of upper bound, written O(n) Referred to as linear time
Doubling problem size doubles running time
Example: linear search; finding largest element in list
David Weir (U of Sussex) Program Analysis Term 1, 2015 52 / 606
Polynomial Time
f(n)=nk forsomek≥1
Expression of upper bound, written O(nk ) Referred to as polynomial time
k is a positive integer
e.g. O(n), O(n2), O(n3), O(n4), . . .
Linear time special case of polynomial time (k = 1) O(n2) is called quadratic
O(n3) is called cubic
Example: O(n2) – selection sort; insertion sort
David Weir (U of Sussex) Program Analysis Term 1, 2015 53 / 606
Exponential Time
f(n) = kn for some k > 1
Expression of upper bound, written O(kn) Referrred to as exponential time Typically k = 2, so O(2n)
Unacceptable running time
Example: Any algorithm that considers all subsets of a set
David Weir (U of Sussex) Program Analysis Term 1, 2015 54 / 606
Logarithmic Time
f(n) = logn
Expression of upper bound, written O(log n)
Referred to as logarithmic time
Grows very slowly
Base of logarithm not important when considering O(.) O(log2 n) same as O(log3 n), . . .
Example: binary search
David Weir (U of Sussex) Program Analysis Term 1, 2015 55 / 606
Another Common Running Time
f (n) = n log n
Expression upper bound, written O(n log n)
Grows only slightly faster than O(n) Example: merge sort
David Weir (U of Sussex) Program Analysis Term 1, 2015 56 / 606
Relative Growth Rates
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < ... < O(2n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 57 / 606
Importance of Running Times
problem size
running time
n nlogn n2 n3 2n n!
10 30 50 100 103 104 105 106
<1s <1s <1s <1s <1s <1s <1s 1s
<1s <1s <1s <1s <1s <1s 2s 20 s
<1s <1s <1s <1s 1s 2m 3h 12 d
<1s <1s <1s 1s 18 m 12 d 32 y 3, 1710 y
<1s
18 m
36 y 1017 y
> 1025 y > 1025 y > 1025 y > 1025 y
4s 1025 y
> 1025 y > 1025 y > 1025 y > 1025 y > 1025 y > 1025 y
assumes 1, 000, 000 instructions per second
David Weir (U of Sussex) Program Analysis Term 1, 2015 58 / 606
Questions for you
Suppose we are told that an algorithm has a running time of O(n3) Question: What does this tell us about how slow the running time is? Question: What does this tell us about how fast the running time is?
David Weir (U of Sussex) Program Analysis Term 1, 2015 59 / 606
Questions for you
Suppose we are told that an algorithm has a running time of O(n3) Question: What does this tell us about how slow the running time is?
The running time is asymptotically no worse than c · n3 for some c Question: What does this tell us about how fast the running time is?
Nothing
David Weir (U of Sussex) Program Analysis Term 1, 2015 59 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n
Suppose this is a plot of the running time t(n) of our algorithm
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n
Can we find a function that will always keep below this one?
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n
Let’s consider a constant function: e.g. f (n) = 10
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n0
After crossing at n0, 10 remains below t(n)
10
n
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n0 So we can say t(n) is Ω(10)
10
n
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n0 Prefer to say t(n) is Ω(1)
10
n
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n0
Let’s try a function that grows faster: e.g. n
10
n
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n0
f(n) = n lies below t(n) after n0
n
n
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n0
So we can also say t(n) is Ω(n)
n
n
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n)
n0
Let’s try a function that grows faster still: e.g. n2
n
n
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
n2
t(n)
n
f(n) = n2 grows faster than t(n)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
60 / 606
Asymptotic Lower Bound: Example
steps
n2
t(n)
n
What about f (n) = 0.75n2? David Weir (U of Sussex)
Program Analysis
Term 1, 2015
60 / 606
Asymptotic Lower Bound: Example
steps
t(n) 0.75n2
n
f(n) = 0.75n2 grows slower than t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound: Example
steps
t(n) 0.75n2
n
So we can say that t(n) is Ω(n2)
David Weir (U of Sussex) Program Analysis Term 1, 2015 60 / 606
Asymptotic Lower Bound
Definition of Ω(g(n)):
t(n) is Ω(f(n)) if
there are constants n0 and c > 0 such that
t(n)≥c·f(n) foralln≥n0
David Weir (U of Sussex) Program Analysis Term 1, 2015 61 / 606
Question for you
Let t(n) = n2 − n
Give values for n0 and c showing that t(n) is Ω(n2)
t(n) is Ω(f(n)) if
there are constants n0 and c > 0 such that
t(n)≥c·f(n) foralln≥n0
David Weir (U of Sussex) Program Analysis Term 1, 2015 62 / 606
Question for you
Let t(n) = n2 − n
Give values for n0 and c showing that t(n) is Ω(n2)
t(n) is Ω(f(n)) if
there are constants n0 and c > 0 such that
t(n)≥c·f(n) foralln≥n0
n0 =4andc=0.75
David Weir (U of Sussex) Program Analysis Term 1, 2015 62 / 606
Asymptotic Tight Bound
Definition of Θ(f (n)): t(n) is Θ(f(n)) if
t(n) is O(f(n)) and t(n) is also Ω(f(n))
David Weir (U of Sussex) Program Analysis Term 1, 2015 63 / 606
Asymptotic Tight Bound: Example
steps
t(n)
n
Same function as previous example
David Weir (U of Sussex) Program Analysis Term 1, 2015 64 / 606
Asymptotic Tight Bound: Example
steps
n2
t(n)
n
f(n) = n2 grows faster than t(n)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
64 / 606
Asymptotic Tight Bound: Example
steps
n2
t(n) 0.75n2
n
f(n) = 0.75n2 grows slower than t(n) David Weir (U of Sussex) Program Analysis
Term 1, 2015
64 / 606
Asymptotic Tight Bound: Example
steps
n2
t(n) 0.75n2
n
So we can say that t(n) is Θ(n2)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
64 / 606
Have we been oversimplifying things?
Question: Is running time really just a function of n?
David Weir (U of Sussex) Program Analysis Term 1, 2015 65 / 606
Have we been oversimplifying things?
Question: Is running time really just a function of n? Answer: Sometimes, but not always
David Weir (U of Sussex) Program Analysis Term 1, 2015 65 / 606
Have we been oversimplifying things?
Question: Is running time really just a function of n? Answer: Sometimes, but not always
Question: What else can running time be a function of?
David Weir (U of Sussex) Program Analysis Term 1, 2015 65 / 606
Have we been oversimplifying things?
Question: Is running time really just a function of n? Answer: Sometimes, but not always
Question: What else can running time be a function of? Answer: Sometimes the values make a difference
David Weir (U of Sussex) Program Analysis Term 1, 2015 65 / 606
Example: The Cases of Searching
Consider algorithm that searches an unordered list for a target value by considering each item in list in turn from first to last
Best-case:
inputs where target value at front of list
running time will be Θ(1) Worst-case:
inputs where target value not in list
running time will be Θ(n) where n is length of list
David Weir (U of Sussex) Program Analysis Term 1, 2015 66 / 606
Worst- Best-Case Difference
steps
worst-case
n
Worst-case of Θ(n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 67 / 606
Worst- Best-Case Difference
steps
worst-case
best-case
n
Best-case of Θ(1) David Weir (U of Sussex)
Program Analysis
Term 1, 2015 67 / 606
Expected- or Average-Case
Expected performance: the running time you would expect on average
Something that is of interest when worst-case and best-case running times are asymptotically different
Difficulty: over what selection of inputs should the calculation take place?
Values making up input (not just its size) matters
Probabilities of each possible input might not form a uniform distribution
Actual distribution once deployed may be unknowable
David Weir (U of Sussex) Program Analysis Term 1, 2015 68 / 606
Expected- or Average-Case: Example
Consider linear search among n items Some of the issues that arise:
Need to know size of set of all the items that could appear in list Can we assume that items in list chosen at random from this set Are items selected from this set with or without replacement
Resolving these issues would allow us to:
Estimate the probability that target item is in a list of size n Estimate the expected number of comparisons
David Weir (U of Sussex) Program Analysis Term 1, 2015 69 / 606
Lower Bound for a Problem
A different kind of question:
what is the lower limit on how efficiently a problem can be solved?
No particular algorithm in mind
This is a property of a problem not of an algorithm This can be a very hard question to answer Requires generalising across all possible algorithms
David Weir (U of Sussex) Program Analysis Term 1, 2015 70 / 606
An Example: Sorting Problem
Question:
What is the lower bound for the sorting problem?
We know we can sort in O(n log n) time — c.f. MergeSort
Can we sort any quicker?
Is it possible that there an algorithm that solves the sorting problem that has a worst-case running time that is better than O(n log n)?
David Weir (U of Sussex) Program Analysis Term 1, 2015 71 / 606
Consider Comparison Sorting Algorithms only
Comparison sorting algorithms sort elements by comparing them with each other
Bucket sort is not a comparison sorting algorithm Fixed set of buckets into which elements placed Buckets hold all elements in a certain range
No comparison between elements
David Weir (U of Sussex) Program Analysis Term 1, 2015 72 / 606
Comparison Sort Decision Tree
Sorting elements (a1, . . . , an)
a1 < a2 YN
a1 < a3 YNYN
a1 < a3
a1