程序代写代做代考 assembly Java decision tree algorithm Program Analysis

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