Program Analysis
Asymptotic Analysis of Algorithms
David Weir (U of Sussex) Program Analysis Term 1, 2017 31 / 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, 2017 32 / 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, 2017 33 / 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, 2017 34 / 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, 2017 35 / 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, 2017 36 / 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, 2017 37 / 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, 2017 38 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
Suppose this is a plot of the running time t(n) of our algorithm
David Weir (U of Sussex) Program Analysis Term 1, 2017 39 / 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, 2017 40 / 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, 2017 40 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
Suppose this is a plot of the running time t(n) of our algorithm
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
Can we find a function that will grow faster than this one?
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
Let’s consider a linear function: e.g. f (n) = n
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
n
f (n) = n isn’t growing as fast as t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
n
Try adding a constant: f (n) = n + 10
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
n + 10
f (n) = n + 10 has the same rate of growth as n
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)
n + 10
Try multiplying n by a constant f (n) = 3n + 10
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)3n + 10
f (n) = 3n + 10 still doesn’t grow as fast as t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)3n + 10
Any straight line (linear function) eventually gets overtaken by t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)3n + 10
Need something that curves upwards: e.g. f (n) = n2
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)n2
After crossing at n0, n
2 remains above t(n)
n0
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)n2
n0
n2 is an asymptotic upper bound for t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)n2
n0
so we say t(n) is O(n2)
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 606
Asymptotic Upper Bound: Example
steps
n
t(n)n2
n0
Note that it doesn’t matter that n2 grows more rapidly than t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 41 / 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, 2017 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
n = 12
David Weir (U of Sussex) Program Analysis Term 1, 2017 42 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
Consider another running time that grows more rapidly
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
Try f (n) = n2 as a possible asymptotic upper bound
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
n2
f (n) = n2 doesn’t seem to be catching up with t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
n2
Try f (n) = n2 + 10
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
n2 + 10
f (n) = n2 + 10 is still not increasing at the required rate
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
n2 + 10
Need something that grows faster
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
n2 + 10
Try f (n) = 3n2
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
3n2
f (n) = 3n2 has adequate growth rate
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
3n2
n0
After crossing at n0, 3n
2 stays ahead
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
3n2
3n2 is an asymptotic upper bound for t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
3n2
We say t(n) is O(n2) (the constant can be dropped)
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
3n2
4n2
Note that 4n2 is also an asymptotic upper bound for t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
3n2
4n2n3
Even n3 counts as an asymptotic upper bound for t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 606
Asymptotic Upper Bound: Another Example
steps
n
t(n)
3n2
4n2n3
So t(n) is also O(n3)
David Weir (U of Sussex) Program Analysis Term 1, 2017 43 / 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) for all n ≥ n0
David Weir (U of Sussex) Program Analysis Term 1, 2017 44 / 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, 2017 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
n0 = 4 and c = 4
David Weir (U of Sussex) Program Analysis Term 1, 2017 45 / 606
Less Significant Terms
Consider the running time:
t(n) = 14n4 + 12n3 log n + 47n2 + 3n + 17
David Weir (U of Sussex) Program Analysis Term 1, 2017 46 / 606
Less Significant Terms
Consider the running time:
t(n) = 14n4 + 12n3 log n + 47n2 + 3n + 17
Compare this to the function
f (n) = 15 · n4
David Weir (U of Sussex) Program Analysis Term 1, 2017 46 / 606
Less Significant Terms
Consider the running time:
t(n) = 14n4 + 12n3 log n + 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, 2017 46 / 606
Less Significant Terms
Consider the running time:
t(n) = 14n4 + 12n3 log n + 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, 2017 46 / 606
Less Significant Terms
Consider the running time:
t(n) = 14n4 + 12n3 log n + 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, 2017 46 / 606
Question for you
What is the lowest value of n where f (n) = 15 · n4 is greater than
t(n) = 14n4 + 12n3 log n + 47n2 + 3n + 17
David Weir (U of Sussex) Program Analysis Term 1, 2017 47 / 606
Question for you
What is the lowest value of n where f (n) = 15 · n4 is greater than
t(n) = 14n4 + 12n3 log n + 47n2 + 3n + 17
n = 76
David Weir (U of Sussex) Program Analysis Term 1, 2017 47 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4
David Weir (U of Sussex) Program Analysis Term 1, 2017 48 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4
t(n) is O(n4)
David Weir (U of Sussex) Program Analysis Term 1, 2017 48 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4
t(n) is O(n4)
Consider the rather different running time
t(n) = 0.000001n4
David Weir (U of Sussex) Program Analysis Term 1, 2017 48 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4
t(n) is O(n4)
Consider the rather different running time
t(n) = 0.000001n4
t(n) is still O(n4)
David Weir (U of Sussex) Program Analysis Term 1, 2017 48 / 606
Ignoring Constants
Consider the running time
t(n) = 100000n4
t(n) is O(n4)
Consider the rather different running time
t(n) = 0.000001n4
t(n) is still O(n4)
Lack of concern for constants is consistent with our lack of concern for
the granularity with which we measure running time
David Weir (U of Sussex) Program Analysis Term 1, 2017 48 / 606
Landmark Growth Rates
We now consider a few of the more common growth rates
David Weir (U of Sussex) Program Analysis Term 1, 2017 49 / 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, 2017 50 / 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, 2017 51 / 606
Polynomial Time
f (n) = nk for some k ≥ 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, 2017 52 / 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, 2017 53 / 606
Logarithmic Time
f (n) = log n
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, 2017 54 / 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, 2017 55 / 606
Relative Growth Rates
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < . . . < O(2n) David Weir (U of Sussex) Program Analysis Term 1, 2017 56 / 606 Importance of Running Times problem running time size n n log n n2 n3 2n n! 10 < 1 s < 1 s < 1 s < 1 s < 1 s 4 s 30 < 1 s < 1 s < 1 s < 1 s 18 m 1025 y 50 < 1 s < 1 s < 1 s < 1 s 36 y > 1025 y
100 < 1 s < 1 s < 1 s 1 s 1017 y > 1025 y
103 < 1 s < 1 s 1 s 18 m > 1025 y > 1025 y
104 < 1 s < 1 s 2 m 12 d > 1025 y > 1025 y
105 < 1 s 2 s 3 h 32 y > 1025 y > 1025 y
106 1 s 20 s 12 d 3, 1710 y > 1025 y > 1025 y
assumes 1, 000, 000 instructions per second
David Weir (U of Sussex) Program Analysis Term 1, 2017 57 / 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, 2017 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?
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, 2017 58 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
Suppose this is a plot of the running time t(n) of our algorithm
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
Can we find a function that will always keep below this one?
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
Let’s consider a constant function: e.g. f (n) = 10
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
10
n0
After crossing at n0, 10 remains below t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
10
n0
So we can say t(n) is Ω(10)
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
10
n0
Prefer to say t(n) is Ω(1)
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
10
n0
Let’s try a function that grows faster: e.g. n
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
n
n0
f (n) = n lies below t(n) after n0
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
n
n0
So we can also say t(n) is Ω(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
n
n0
Let’s try a function that grows faster still: e.g. n2
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)n2
f (n) = n2 grows faster than t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)n2
What about f (n) = 0.75n2?
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
0.75n2
f (n) = 0.75n2 grows slower than t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound: Example
steps
n
t(n)
0.75n2
So we can say that t(n) is Ω(n2)
David Weir (U of Sussex) Program Analysis Term 1, 2017 59 / 606
Asymptotic Lower Bound
Definition of Ω(f (n)):
t(n) is Ω(f (n)) if
there are constants n0 and c > 0 such that
t(n) ≥ c · f (n) for all n ≥ n0
David Weir (U of Sussex) Program Analysis Term 1, 2017 60 / 606
Question for you
Let t(n) = n2 − n
Give values for n0 and c showing that t(n) is Ω(n
2)
t(n) is Ω(f (n)) if
there are constants n0 and c > 0 such that
t(n) ≥ c · f (n) for all n ≥ n0
David Weir (U of Sussex) Program Analysis Term 1, 2017 61 / 606
Question for you
Let t(n) = n2 − n
Give values for n0 and c showing that t(n) is Ω(n
2)
t(n) is Ω(f (n)) if
there are constants n0 and c > 0 such that
t(n) ≥ c · f (n) for all n ≥ n0
n0 = 4 and c = 0.75
David Weir (U of Sussex) Program Analysis Term 1, 2017 61 / 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, 2017 62 / 606
Asymptotic Tight Bound: Example
steps
n
t(n)
Same function as previous example
David Weir (U of Sussex) Program Analysis Term 1, 2017 63 / 606
Asymptotic Tight Bound: Example
steps
n
t(n)n2
f (n) = n2 grows faster than t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 63 / 606
Asymptotic Tight Bound: Example
steps
n
t(n)n2
0.75n2
f (n) = 0.75n2 grows slower than t(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 63 / 606
Asymptotic Tight Bound: Example
steps
n
t(n)n2
0.75n2
So we can say that t(n) is Θ(n2)
David Weir (U of Sussex) Program Analysis Term 1, 2017 63 / 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, 2017 64 / 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, 2017 64 / 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, 2017 64 / 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, 2017 64 / 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, 2017 65 / 606
Worst- Best-Case Difference
steps
n
worst-case
Worst-case of Θ(n)
David Weir (U of Sussex) Program Analysis Term 1, 2017 66 / 606
Worst- Best-Case Difference
steps
n
worst-case
best-case
Best-case of Θ(1)
David Weir (U of Sussex) Program Analysis Term 1, 2017 66 / 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, 2017 67 / 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, 2017 68 / 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, 2017 69 / 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, 2017 70 / 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, 2017 71 / 606
Comparison Sort Decision Tree
Sorting elements (a1, . . . ,an)
a1 < a2 a1 < a3 Y a1 < a4 Y an−1 < an Y N a1 < a4 N an−1 < an Y N a1 < a3 N a1 < a4 Y an−1 < an Y N a1 < a4 N an−1 < an Y N There are n! leaves — one for each permutation David Weir (U of Sussex) Program Analysis Term 1, 2017 72 / 606 Implications of Decision Tree The height of the decision tree gives lower bound on length of computations There must be a distinct computation path for each root to leaf path in the tree — otherwise algorithm is not correct How long must an algorithm’s computations be if it is capable of distinguishing so many alternatives? David Weir (U of Sussex) Program Analysis Term 1, 2017 73 / 606 Analysis of Decision Tree Decision tree has n! leaves Height is at least log n! n! has at least n 2 terms that are at least n 2 So log n! ≥ log ( n 2 n 2 ) log(n 2 n 2 ) = n 2 log n 2 n 2 log n 2 is O(n log n) Lower bound for comparison-based sorting is O(n log n) David Weir (U of Sussex) Program Analysis Term 1, 2017 74 / 606 Question for you Why is it not strictly correct to start a sentence as follows. ◮ The asymptotic upper bound for the running time of the algorithm is . . . David Weir (U of Sussex) Program Analysis Term 1, 2017 75 / 606 Question for you Why is it not strictly correct to start a sentence as follows. ◮ The asymptotic upper bound for the running time of the algorithm is . . . There can never be just one asymptotic upper bound, so the definite article “the” is not appropriate. An asymptotic upper bound for the running time of the algorithm is . . . David Weir (U of Sussex) Program Analysis Term 1, 2017 75 / 606 Question for you Does it make sense to specify either of the following? Explain your answer. ◮ An asymptotic lower bound on the worst-case running time of an algorithm; ◮ An asymptotic upper bound on the best-case running time of an algorithm. David Weir (U of Sussex) Program Analysis Term 1, 2017 76 / 606 Question for you Does it make sense to specify either of the following? Explain your answer. ◮ An asymptotic lower bound on the worst-case running time of an algorithm; ◮ An asymptotic upper bound on the best-case running time of an algorithm. Yes. An asymptotic lower bound on the worst-case running time gives a constraint on how fast the algorithm could run when exhibiting its worst-case behaviour, and an asymptotic upper bound on the best-case running time gives a constraint on how slow the algorithm could run when exhibiting its best-case behaviour David Weir (U of Sussex) Program Analysis Term 1, 2017 76 / 606 Question for you Give an example of an algorithm for which an asympotic lower bound for the worst-case running time is not also an asympotic lower bound for the running time in general. David Weir (U of Sussex) Program Analysis Term 1, 2017 77 / 606 Question for you Give an example of an algorithm for which an asympotic lower bound for the worst-case running time is not also an asympotic lower bound for the running time in general. An algorithm that performs linear left-to-right search of a sequence of length n for a value. An asymptotic lower bound on worst-case is Ω(n), but this is not a lower bound for the algorithm in general. David Weir (U of Sussex) Program Analysis Term 1, 2017 77 / 606 Question for you Are upper and lower bounds for the running time of an algorithm also upper and lower bounds for the worst-case running time of an algorithm and upper and lower bounds for the best-case running time of an algorithm? David Weir (U of Sussex) Program Analysis Term 1, 2017 78 / 606 Question for you Are upper and lower bounds for the running time of an algorithm also upper and lower bounds for the worst-case running time of an algorithm and upper and lower bounds for the best-case running time of an algorithm? Yes, though they may not be as tight as the bounds that could be given for the worst- or best-case running times. David Weir (U of Sussex) Program Analysis Term 1, 2017 78 / 606