程序代写代做代考 algorithm 04.key

04.key

http://people.eng.unimelb.edu.au/tobym

@tobycmurray

toby.murray@unimelb.edu.au

DMD 8.17 (Level 8, Doug McDonell Bldg)

Toby Murray

COMP90038 

Algorithms and Complexity

Lecture 4: Analysis of Algorithms
(with thanks to Harald Søndergaard)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Last Time: Time Complexity
• Measure input size by natural number n

• Measure execution time as number of basic
operations performed

• Time complexity t(n) for an algorithm: number of
basic operations as a function of n

• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Establishing Growth Rate
• In the last lecture we proved t(n) ∈ O(g(n)) for some

cases of t and g, using the definition of O directly: 


n >n0 ⇒ t(n) < c ·g(n) for some c and n0. • A more common approach uses 
 • lim = 
 • Use this to show that 1000n ∈ O(n2) 3 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n 1000n ∈ O(n2) 4 n→∞ lim n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n 1000n ∈ O(n2) 4 n→∞ lim n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n 1000n ∈ O(n2) 4 n→∞ lim n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n 1000n ∈ O(n2) 4 n→∞ lim n2 = 1000n→∞lim n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n 1000n ∈ O(n2) 4 n→∞ lim n2 = 1000n→∞lim n = 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n 1000n ∈ O(n2) 4 n→∞ lim n2 = 1000n→∞lim n = 0 So 1000n grows asymptotically slower than n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n 1000n ∈ O(n2) 4 n→∞ lim n2 = 1000n→∞lim n = 0 So 1000n grows asymptotically slower than n2 Thus 1000n ∈ O(n2) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ • lim = 5 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ • lim = 5 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) f(n) ∈ O(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ • lim = 5 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) f(n) ∈ O(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ • lim = 5 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) f(n) ∈ O(g(n)) f(n) ∈ Ω(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ • lim = 5 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) f(n) ∈ O(g(n)) f(n) ∈ Ω(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ • lim = 5 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) f(n) ∈ O(g(n)) f(n) ∈ Ω(g(n)) f(n) ∈ Θ(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ • lim = 5 n→∞ f(n) g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) f(n) ∈ O(g(n)) f(n) ∈ Ω(g(n)) f(n) ∈ Θ(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule • For example, show that log2 n grows slower than 
 
 
 
 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) n where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule • For example, show that log2 n grows slower than 
 
 
 
 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) n lim n→∞ log2 n n where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule • For example, show that log2 n grows slower than 
 
 
 
 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) n lim n→∞ log2 n n = lim n→∞ (loge 2) 1 n 1 2 n where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule • For example, show that log2 n grows slower than 
 
 
 
 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) n lim n→∞ log2 n n = lim n→∞ (loge 2) 1 n 1 2 n = lim n→∞ ((loge 2) 1 n ⋅ 2 n) where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule • For example, show that log2 n grows slower than 
 
 
 
 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) n lim n→∞ log2 n n = lim n→∞ (loge 2) 1 n 1 2 n = lim n→∞ ((loge 2) 1 n ⋅ 2 n) = 2 loge 2 lim n→∞ n n where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule • For example, show that log2 n grows slower than 
 
 
 
 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) n lim n→∞ log2 n n = lim n→∞ (loge 2) 1 n 1 2 n = lim n→∞ ((loge 2) 1 n ⋅ 2 n) = 2 loge 2 lim n→∞ n n = 2 loge 2 lim n→∞ 1 n where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule • For example, show that log2 n grows slower than 
 
 
 
 6 lim h→∞ t(n) g(n) = lim h→∞ t′�(n) g′ �(n) n lim n→∞ log2 n n = lim n→∞ (loge 2) 1 n 1 2 n = lim n→∞ ((loge 2) 1 n ⋅ 2 n) = 2 loge 2 lim n→∞ n n = 2 loge 2 lim n→∞ 1 n = 0 where t’ and g’ are the derivatives of t and g Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] 42 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] 42 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] 42 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] 4269 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] 4269 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array 7 23 12 42 6 69 18 3A: max: 23 A[i] 4269 (where n is length of the array) 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(n) = Example: Finding Largest Element in an Array 8 (where n is length of the array) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(n) = Example: Finding Largest Element in an Array 8 (where n is length of the array) Size of input, n: length of the array Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(n) = Example: Finding Largest Element in an Array 8 (where n is length of the array) Size of input, n: length of the array Basic operation: comparison “A[i] > max”

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

C(n) =

Example:
Finding Largest Element in an Array

8

(where n is length of
the array)

Size of input, n:
length of the array

Basic operation: comparison “A[i] > max”
Count the number of basic operations executed
for an array of size n:

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

C(n) =

Example:
Finding Largest Element in an Array

8

(where n is length of
the array)

Size of input, n:
length of the array

Basic operation: comparison “A[i] > max”
Count the number of basic operations executed
for an array of size n:

n−1


i=1

1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

C(n) =

Example:
Finding Largest Element in an Array

8

(where n is length of
the array)

Size of input, n:
length of the array

Basic operation: comparison “A[i] > max”
Count the number of basic operations executed
for an array of size n:

n−1


i=1

1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

C(n) =

Example:
Finding Largest Element in an Array

8

(where n is length of
the array)

Size of input, n:
length of the array

Basic operation: comparison “A[i] > max”
Count the number of basic operations executed
for an array of size n:

n−1


i=1

1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

C(n) =

Example:
Finding Largest Element in an Array

8

(where n is length of
the array)

Size of input, n:
length of the array

Basic operation: comparison “A[i] > max”
Count the number of basic operations executed
for an array of size n:

n−1


i=1

1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

C(n) =

Example:
Finding Largest Element in an Array

8

(where n is length of
the array)

Size of input, n:
length of the array

Basic operation: comparison “A[i] > max”
Count the number of basic operations executed
for an array of size n:

n−1


i=1

1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

C(n) =

Example:
Finding Largest Element in an Array

8

(where n is length of
the array)

Size of input, n:
length of the array

Basic operation: comparison “A[i] > max”
Count the number of basic operations executed
for an array of size n:

n−1


i=1

1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min: 0
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

1

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

1

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

1

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

13

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

13

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

13

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

13

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

9

23 12 42 6 69 18 3

A[i]

min:

A[j]

0
0 1 2 3 4 5 6

136

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

10

3 12 42 6 69 18 23

A[i]

min: 03
0 1 2 3 4 5 6

6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

10

3 12 42 6 69 18 23

A[i]

min: 03
0 1 2 3 4 5 6

6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

min: 1
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

min:

A[j]

1
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

min:

A[j]

1
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

min:

A[j]

13
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

min:

A[j]

13
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

min:

A[j]

13
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

11

3 12 42 6 69 18 23

A[i]

min:

A[j]

13
0 1 2 3 4 5 6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

12

3 6 42 12 69 18 23

A[i]

min: 03
0 1 2 3 4 5 6

3

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

12

3 6 42 12 69 18 23

A[i]

min: 03
0 1 2 3 4 5 6

3

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort

13

Input size n: length
of the array

Basic operation:
comparison A[j] < A[min] Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Selection Sort 13 Input size n: length of the array Basic operation: comparison A[j] < A[min] C(n) = Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Selection Sort 13 Input size n: length of the array Basic operation: comparison A[j] < A[min] C(n) = n−2 ∑ i=0 n−1 ∑ j=i+1 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Selection Sort 13 Input size n: length of the array Basic operation: comparison A[j] < A[min] C(n) = n−2 ∑ i=0 n−1 ∑ j=i+1 1 = n−2 ∑ i=0 (n − 1 − i) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Selection Sort 13 Input size n: length of the array Basic operation: comparison A[j] < A[min] C(n) = n−2 ∑ i=0 n−1 ∑ j=i+1 1 = n−2 ∑ i=0 (n − 1 − i) = n−2 ∑ i=0 (n − 1) − n−2 ∑ i=0 i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Selection Sort 13 Input size n: length of the array Basic operation: comparison A[j] < A[min] C(n) = n−2 ∑ i=0 n−1 ∑ j=i+1 1 = n−2 ∑ i=0 (n − 1 − i) = n−2 ∑ i=0 (n − 1) − n−2 ∑ i=0 i = (n − 1)2 − (n − 2)(n − 1) 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Selection Sort 13 Input size n: length of the array Basic operation: comparison A[j] < A[min] C(n) = n−2 ∑ i=0 n−1 ∑ j=i+1 1 = n−2 ∑ i=0 (n − 1 − i) = n−2 ∑ i=0 (n − 1) − n−2 ∑ i=0 i = (n − 1)2 − (n − 2)(n − 1) 2 = n(n − 1) 2 ∈ Θ(n2) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C i: 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C i: 0 j: 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 0 k: 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 0 k: 0 40 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 0 k: 0 40 k: 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 14 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 0 k: 0 40 k: 1 103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 15 5 7 3 4 8 2 9 6 A B C i: 0 j: 1 103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 15 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 1 103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 15 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 1 k: 0 103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 15 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 1 k: 0 10103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 15 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 1 k: 0 10 k: 1 103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 15 5 7 3 4 8 2 9 6 A B C 0 i: 0 j: 1 k: 0 10 k: 1 103 52 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) = n−1 ∑ i=0 n−1 ∑ j=0 n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) = n−1 ∑ i=0 n−1 ∑ j=0 n = n−1 ∑ i=0 n−1 ∑ j=0 (n ⋅ 1) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) = n−1 ∑ i=0 n−1 ∑ j=0 n = n−1 ∑ i=0 n−1 ∑ j=0 (n ⋅ 1) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) = n−1 ∑ i=0 n−1 ∑ j=0 n = n−1 ∑ i=0 n−1 ∑ j=0 (n ⋅ 1) = n−1 ∑ i=0 n ⋅ n−1 ∑ j=0 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) = n−1 ∑ i=0 n−1 ∑ j=0 n = n−1 ∑ i=0 n−1 ∑ j=0 (n ⋅ 1) = n−1 ∑ i=0 n ⋅ n−1 ∑ j=0 1 = n−1 ∑ i=0 n2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) = n−1 ∑ i=0 n−1 ∑ j=0 n = n−1 ∑ i=0 n−1 ∑ j=0 (n ⋅ 1) = n−1 ∑ i=0 n ⋅ n−1 ∑ j=0 1 = n−1 ∑ i=0 n2 = n3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 17 M(n) = n−1 ∑ i=0 n−1 ∑ j=0 n−1 ∑ k=0 1 = n−1 ∑ i=0 n−1 ∑ j=0 ((n − 1) − 0 + 1) = n−1 ∑ i=0 n−1 ∑ j=0 n = n−1 ∑ i=0 n−1 ∑ j=0 (n ⋅ 1) = n−1 ∑ i=0 n ⋅ n−1 ∑ j=0 1 = n−1 ∑ i=0 n2 = n3 ∈ Θ(n3) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) = F(4) ⋅ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) = F(4) ⋅ 5 = (F(3) ⋅ 4) ⋅ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) = F(4) ⋅ 5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) = F(4) ⋅ 5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) = F(4) ⋅ 5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) = F(4) ⋅ 5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 18 F(5) = F(4) ⋅ 5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = 5! Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = 0 M(n) = Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = 0 M(n) = M(n − 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = 0 M(n) = M(n − 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = 0 M(n) = M(n − 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = 0 M(n) = M(n − 1) + 1 Need to express M(n) in closed form (i.e. non-recursively) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive
 Algorithms 19 Basic operation: multiplication We express the cost recursively (as a recurrence relation) M(0) = 0 M(n) = M(n − 1) + 1 Need to express M(n) in closed form (i.e. non-recursively) Try: “telescoping” aka “backward substitution” Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … = M(n − n) + n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … = M(n − n) + n = M(0) + n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … = M(n − n) + n = M(0) + n = n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … = M(n − n) + n = M(0) + n = n Closed form: Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … = M(n − n) + n = M(0) + n = n Closed form: M(n) = n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … = M(n − n) + n = M(0) + n = n Closed form: M(n) = n Complexity: Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping
 (aka Backward Substitution) 20 M(0) = 0M(n) = M(n − 1) + 1 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 M(n) = (M(n − 2) + 1) + 1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 … = M(n − n) + n = M(0) + n = n Closed form: M(n) = n Complexity: M(n) ∈ Θ(n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 21 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 21 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,0,6,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 21 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,0,6,41) lo: 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 21 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,0,6,41) lo: 0 hi: 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 21 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,0,6,41) lo: 0 hi: 6 key: 41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 21 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,0,6,41) lo: 0 hi: 6 key: 41 mid: 3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 21 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,0,6,41) lo: 0 hi: 6 key: 41 mid: 3 BinSearch(A,4,6,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 22 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,6,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 22 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,6,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 22 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,6,41) lo: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 22 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,6,41) lo: 4 hi: 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 22 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,6,41) lo: 4 hi: 6 key: 41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 22 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,6,41) lo: 4 hi: 6 key: 41 mid: 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 22 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,6,41) lo: 4 hi: 6 key: 41 mid: 5 BinSearch(A,4,4,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 23 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,4,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 23 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,4,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 23 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,4,41) lo: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 23 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,4,41) lo: 4 hi: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 23 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,4,41) lo: 4 hi: 4 key: 41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 23 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,4,41) lo: 4 hi: 4 key: 41 mid: 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array 23 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,4,4,41) lo: 4 hi: 4 key: 41 mid: 4 returns 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array Basic operation: key comparison A[mid] = key Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(0) = Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(0) = 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(0) = 0 C(n) = C(n/2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(0) = 0 C(n) = C(n/2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 A smoothness rule allows us to assume that n is a power of 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 A smoothness rule allows us to assume that n is a power of 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 A smoothness rule allows us to assume that n is a power of 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 A smoothness rule allows us to assume that n is a power of 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 … A smoothness rule allows us to assume that n is a power of 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 … = C(n/n) + log2 n A smoothness rule allows us to assume that n is a power of 2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 … = C(n/n) + log2 n A smoothness rule allows us to assume that n is a power of 2 = (C(0) + 1) + log2 n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 … = C(n/n) + log2 n A smoothness rule allows us to assume that n is a power of 2 = (C(0) + 1) + log2 n = 1 + log2 n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 … = C(n/n) + log2 n A smoothness rule allows us to assume that n is a power of 2 = (C(0) + 1) + log2 n = 1 + log2 n C(n) ∈ Θ(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions 
 Have Same Rate of Growth 26 In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions 
 Have Same Rate of Growth 26 In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim n→∞ logan logbn = lim n→∞ (loga b)(logb n) logb n = (loga b) lim n→∞ 1 = loga b Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions 
 Have Same Rate of Growth 26 In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim n→∞ logan logbn = lim n→∞ (loga b)(logb n) logb n = (loga b) lim n→∞ 1 = loga b So, e.g.: Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions 
 Have Same Rate of Growth 26 In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim n→∞ logan logbn = lim n→∞ (loga b)(logb n) logb n = (loga b) lim n→∞ 1 = loga b O(logan) = O(logbn)So, e.g.: Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions 
 Have Same Rate of Growth 26 In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim n→∞ logan logbn = lim n→∞ (loga b)(logb n) logb n = (loga b) lim n→∞ 1 = loga b O(logan) = O(logbn)So, e.g.: Also, since Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions 
 Have Same Rate of Growth 26 In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim n→∞ logan logbn = lim n→∞ (loga b)(logb n) logb n = (loga b) lim n→∞ 1 = loga b O(logan) = O(logbn)So, e.g.: Also, since log nc = c ⋅ log n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions 
 Have Same Rate of Growth 26 In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim n→∞ logan logbn = lim n→∞ (loga b)(logb n) logb n = (loga b) lim n→∞ 1 = loga b O(logan) = O(logbn)So, e.g.: Also, since log nc = c ⋅ log n log nc ∈ O(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Back to Euclid 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Back to Euclid 27 Running time is linear in size (in bits) of input, i.e. O(log(m + n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Back to Euclid 27 Running time is linear in size (in bits) of input, i.e. O(log(m + n)) since the value of m (and n) is at least halved in every two iterations. Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Back to Euclid 27 Running time is linear in size (in bits) of input, i.e. O(log(m + n)) since the value of m (and n) is at least halved in every two iterations. Why? After two iterations, m becomes m mod n; also 1 < n < m ⟹ m mod n < m/2 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Then the following hold: Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}) t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Then the following hold: Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}) t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Then the following hold: (we can throw away smaller summands) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}) t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Then the following hold: c ⋅ t1(n) ∈ O(g1(n)) (we can throw away smaller summands) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}) t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Then the following hold: c ⋅ t1(n) ∈ O(g1(n)) (we can throw away smaller summands) (constants can be thrown away too) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}) t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Then the following hold: c ⋅ t1(n) ∈ O(g1(n)) t1(n) ⋅ t2(n) ∈ O(g1(n) ⋅ g2(n)) (we can throw away smaller summands) (constants can be thrown away too) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Summarising Reasoning with Big-Oh 28 Suppose t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}) t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n)) Then the following hold: c ⋅ t1(n) ∈ O(g1(n)) t1(n) ⋅ t2(n) ∈ O(g1(n) ⋅ g2(n)) (we can throw away smaller summands) (constants can be thrown away too) (for nested loops: count number of times outer loop 
 is executed, multiply by cost of inner loop) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Some Useful Formulas 29 From Stirling’s formula: n! ∈ O(nn+ 1 2 ) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Some Useful Formulas 29 From Stirling’s formula: n! ∈ O(nn+ 1 2 ) this is not the time complexity of an algorithm to compute n-factorial Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Some Useful Formulas 29 From Stirling’s formula: n! ∈ O(nn+ 1 2 ) this is not the time complexity of an algorithm to compute n-factorial Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Some Useful Formulas 29 From Stirling’s formula: n! ∈ O(nn+ 1 2 ) this is not the time complexity of an algorithm to compute n-factorial See also Cormen’s Appendix A or Levitin’s Appendix A. Levitin’s Appendix B is a tutorial on recurrence relations. Copyright University of Melbourne 2016, provided under Creative Commons Attribution License The Road Ahead • You’ll get much more familiar with asymptotic analysis as we use it on algorithms we meet in this course. • Next week we begin our study of algorithms by looking at brute force approaches 30