CS计算机代考程序代写 AI algorithm Microsoft PowerPoint - CSE101 B Time Complexity and Proving Correctness of Algorithms.pptx

Microsoft PowerPoint – CSE101 B Time Complexity and Proving Correctness of Algorithms.pptx

1Appendix B
Time Complexity
and Correctness

Time complexity

Big O and its relatives

2Appendix B
Time Complexity
and Correctness

Definition of Big O

For functions

we say

to mean there are constants, C and k such that

for all n > k.

Example: What constants can we use to prove that?
A. C = 1/3, k = 2
B. C = 5, k = 1
C. C = 10, k = 2
D. None: f(n) isn’t big O of g(n)

f(n) is big O of g(n)

3n2+2n is big O of n2

3Appendix B
Time Complexity
and Correctness

Other asymptotic classes

means there are constants C and k such that

for all n > k.

means

and

Big O is an
upper bound.

Big  is a
lower bound.

Big  is a
tight bound.

4Appendix B
Time Complexity
and Correctness

Big O and its relatives

Exercise: Which is true?

5Appendix B
Time Complexity
and Correctness

Big O: How to compute?

Drop constants:

• It is important to distinguish constants from variables. Both are numbers.

• What makes a number a “constant”?

• Just as we discussed when we listed “single‐step“‐operations,
a constant is a number that doesn’t change as the input grows.

• So 7 is a constant, as is “the time taken by a compare operation”.

• “The time taken to run one pass of BubbleSort” is NOT a constant, because
it will increase as the input array grows in size.

6Appendix B
Time Complexity
and Correctness

Big O: How to compute?

Is f(n) is big O of g(n)? i.e. Is ?

Approach 1: Look for constants C and k.
Approach 2: Use properties

Domination If f(n) <= g(n) for all n then f(n) is big‐O of g(n). Transitivity If f(n) is big‐O of g(n), and g(n) is big‐O of h(n), then f(n) is big‐O of h(n). Additivity/ Multiplicativity If f(n) is big‐O of g(n), and if h(n) is nonnegative, then f(n) * h(n) is big‐O of g(n) * h(n) … where * is either addition or multiplication. Sum is maximum f(n)+g(n) is big‐O of the max(f(n), g(n)) Ignoring constants For any constant c, cf(n) is big‐O of f(n). Approach 3: The limit method. Consider the limit If this limit exists and is 0: then f(n) grows strictly slower than g(n). If this limit exists and is a constant c > 0: then f(n), g(n), grow at the same rate.
If the limit tends to infinity: then f(n) grows strictly faster than g(n).
if the limit doesn’t exist for a different reason … use another approach.

7Appendix B
Time Complexity
and Correctness

Big O: How to compute?

Is f(n) is big O of g(n)? i.e. Is ?

Approach 1: Look for constants C and k.
Approach 2: Use properties

Rosen pp. 210‐213

Look at terms one‐by‐one and
drop constants. Then only

keep maximum.

8Appendix B
Time Complexity
and Correctness

Big O: How to compute?

9Appendix B
Time Complexity
and Correctness

Big O: Examples (1/5)

Let f(n) = n2 + 2n + 1. Find a simpler function of the same order.
f(n) = n2 + 2n + 1 is O(n2) “big O of g(n) = n2” for all n > k.

10Appendix B
Time Complexity
and Correctness

Big O: Examples (1/5)

Let f(n) = n2 + 2n + 1. Find a simpler function of the same order.
f(n) = n2 + 2n + 1 is O(n2) “big O of g(n) = n2”

n2 + 2n + 1
< n2 + 2n2 + n2 (for n > 1)
< 4n2 Witnesses: k = 1 C = 4 Other Witnesses: k = 100 C = 100 k for all n > k.

11Appendix B
Time Complexity
and Correctness

Big O: Examples (2/5)

f(n) = 7n2 is O(n3)

for all n > k.

12Appendix B
Time Complexity
and Correctness

Big O: Examples (2/5)

f(n) = 7n2 is O(n3)

7n2
< n3 (for n > 7)

Witnesses:
k = 7
C = 1

Other Witnesses:
k = 100
C = 100

for all n > k.

13Appendix B
Time Complexity
and Correctness

Big O: Examples (3/5)

f(n) = n2 log n + 3n2 + 3n is O(n2 log n)

for all n > k.

log n = log2n

14Appendix B
Time Complexity
and Correctness

Big O: Examples (3/5)

f(n) = n2 log n + 3n2 + 3n is O(n2 log n)

n2 log n + 3n2 + 3n
< n2 log n + 3n2 log n + 3n2 log n (for n > 2)
< 7 n2 log n Witnesses: k = 2 C = 7 Other Witnesses: k = 100 C = 100 for all n > k.

log n = log2n

15Appendix B
Time Complexity
and Correctness

Big O: Examples (4/5)

f(n) = n! is O(nn)

for all n > k.

log n = log2n

16Appendix B
Time Complexity
and Correctness

Big O: Examples (4/5)

f(n) = n! is O(nn)

n . (n-1) . (n-2) . … . 2 .1
< n . n . n . … . n . n (for n > 1)
< nn Witnesses: k = 1 C = 1 ----------------------------------------------------------------- This implies that f(n) = log n! is big O(n log n). ----------------------------------------------------------------- for all n > k.

log n = log2n

17Appendix B
Time Complexity
and Correctness

Big O: Examples (5/5)

Sum of the first n natural numbers:

1 + 2 + … + n-1 + n = n(n+1)/2

Rewrite this formula
in order notation:

A. O(n)
B. O(n(n+1))
C. O(n2)
D. O(1/2)
E. None of the above

for all n > k.

18Appendix B
Time Complexity
and Correctness

Big O: Examples (5/5)

Sum of the first n natural numbers:

1 + 2 + … + n-1 + n = n(n+1)/2

Rewrite this formula
in order notation:

A. O(n)
B. O(n(n+1))
C. O(n2)
D. O(1/2)
E. None of the above

for all n > k.

C.
1 + 2 + … + n-1 + n = n(n+1)/2

< n + n + … + n + n (for n > 1)
< n2 Witnesses: k = 1 C = 1 B. n(n+1)/2 < n(n+1) (for n > 1)

Witnesses:
k = 1
C = 1

19Appendix B
Time Complexity
and Correctness

Big O is just an upper bound

Big O is an upper bound, not the exact amount of time.

Sometimes, this bound is not tight, i.e., there are sometimes
smaller upper bounds that might be also true.

We will come back to this later in the class.

20Appendix B
Time Complexity
and Correctness

Iterative algorithms 1

Minsort

21Appendix B
Time Complexity
and Correctness

Sorting

1. What problem are we solving? problem specification
2. How do we solve the problem? algorithm description
3. Why do these steps solve the problem? proof of correctness
4. When do we get an answer? time analysis

• Problem Specification
Sorting:

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

22Appendix B
Time Complexity
and Correctness

Sorting

• Problem Specification
Sorting: Given an array A[1], A[2], A[3], … , A[n],
rearrange the values in A so that A[1] < A[2] < A[3] < ... < A[n]. • We usually think of A as an integer array, but really A can contain any set of elements with an underlying total order. • Remember, an algorithm must be well‐defined, terminate, and produce the correct result. A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 23Appendix B Time Complexity and Correctness Minsort 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis 1. 2. 3. 4. 5. 6. 7. 8. 9. 24Appendix B Time Complexity and Correctness Minsort 1. 2. 3. 4. 5. 6. 7. 8. 9. A[1] A[2] A[3] A[4] 49 29 3 25 k=1 3 29 49 25 k=2 3 25 49 29 k=3 3 25 29 49 Find the minimum of the elements at positions k..n (n‐k+1 numbers) together with its position. 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis 25Appendix B Time Complexity and Correctness Minsort 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis 1. 2. 3. 4. 5. 6. 7. 8. 9. A[1] A[2] A[3] A[4] 49 29 3 25 k=1 3 29 49 25 k=2 3 25 49 29 k=3 3 25 29 49 Swap the elements at positions index (where the min is) and k. 26Appendix B Time Complexity and Correctness Minsort 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis Questions: • What makes this algorithm work? • How do you know that the resulting array will be sorted? 1. 2. 3. 4. 5. 6. 7. 8. 9. 27Appendix B Time Complexity and Correctness Correctness proofs 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis 28Appendix B Time Complexity and Correctness Minsort: Correctness (1) 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis 1. 2. 3. 4. 5. 6. 7. 8. 9. Correctness proofs with Loop Invariants: • A Loop Invariant is a property that remains true each time a loop is executed. • To prove an iterative algorithm correct, we must identify a Loop Invariant that implies the following: When the loop is finished, the algorithm has found a solution to the problem. 29Appendix B Time Complexity and Correctness Minsort: Correctness (2) 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis 1. 2. 3. 4. 5. 6. 7. 8. 9. Loop invariant: After the kth time through the outer for‐loop, the first k positions A[1] through A[k] contain the k smallest array elements in order. 30Appendix B Time Complexity and Correctness Loop invariant: After the kth time through the outer for‐loop, the first k positions A[1] through A[k] contain the k smallest array elements in order. • How can we show that this loop invariant is true?  Induction on the number of times through the loop. • Base case: k=0, before the loop. • Induction hypothesis: Suppose the invariant holds after k‐1 times through the loop. • Inductive step: Show that the invariant holds after k times through the loop. • Termination: After k=n‐1 runs. Minsort: Correctness (2) 1. What problem are we solving? problem specification 2. How do we solve the problem? algorithm description 3. Why do these steps solve the problem? proof of correctness 4. When do we get an answer? time analysis 1. 2. 3. 4. 5. 6. 7. 8. 9. 31Appendix B Time Complexity and Correctness Minsort: Correctness (3) Loop Invariant: After the kth time through the outer for-loop, the first k positions A[1] through A[k] contain the k smallest array elements in order. We distinguish between small numbers (all sorted) and big numbers (all unsorted). All big numbers are > to all small numbers.

32Appendix B
Time Complexity
and Correctness

Minsort: Correctness (3)

Loop Invariant: After the kth time through the outer for-loop, the first k positions A[1] through A[k]
contain the k smallest array elements in order.
We distinguish between small numbers (all sorted) and big numbers (all unsorted).
All big numbers are > to all small numbers.

Induction Base (k=0): Before we enter the outer for-loop for the first time,
all numbers are big numbers, i.e. unsorted.

big numbers (unsorted)
A[1] A[n]

33Appendix B
Time Complexity
and Correctness

Minsort: Correctness (3)

Induction Base (k=0): Before we enter the outer for-loop for the first time,
all numbers are big numbers, i.e. unsorted.

Induction Hypothesis: Same as Loop Invariant for iteration k-1.

big numbers (unsorted)
A[1] A[n]

small numbers (sorted)
A[1] A[k-1] A[k] A[n]

big numbers (unsorted)

34Appendix B
Time Complexity
and Correctness

Minsort: Correctness (3)

Induction Base (k=0): Before we enter the outer for-loop for the first time,
all numbers are big numbers, i.e. unsorted.

Induction Hypothesis: Same as Loop Invariant for iteration k-1.

Induction Step:
• Line 2-3: min = first of the big (unsorted) numbers (at position A[k]), index = position of min.
• Inner for-loop (lines 4..7): j runs from k+1 to n (i.e. through the big numbers) and if the next number

at position A[j] is smaller than the current min, this number becomes the new min (min=A[j]) and is
stored together with its position (index=j).

• Lines 8..9: min (at position index) is swapped
with the number at position k, i.e. min is
moved to the front of the big numbers.

big numbers (unsorted)
A[1] A[n]

small numbers (sorted)
A[1] A[k-1] A[k] A[n]

big numbers (unsorted)

A[k] min=A[index]

35Appendix B
Time Complexity
and Correctness

Minsort: Correctness (4)

Loop Invariant: After the kth iteration through the outer for-loop, the last k positions A[n-k+1] .. A[k]
contain the k largest array elements in sorted order.

Induction Step (continued):
• min is the smallest of the big numbers and therefore < to all big numbers, min is > all small numbers

as all big numbers are > all small numbers.
• The set of big numbers has been decreased by 1 and the set of small numbers has been increased by 1.

With the help of the Induction Hypothesis, now the first k numbers A[1..k] are in sorted order.

small numbers (sorted)
A[1] A[k-1] A[k] A[n]

big numbers (unsorted)

small numbers (sorted)
A[1] A[k] A[k+1] A[n]

big numbers (unsorted)

36Appendix B
Time Complexity
and Correctness

Minsort: Correctness (4)

Loop Invariant: After the kth iteration through the outer for-loop, the last k positions A[n-k+1] .. A[k]
contain the k largest array elements in sorted order.

Induction Step (continued):
• min is the smallest of the big numbers and therefore < to all big numbers, min is > all small numbers

as all big numbers are > all small numbers.
• The set of big numbers has been decreased by 1 and the set of small numbers has been increased by 1.

With the help of the Induction Hypothesis, now the first k numbers A[1..k] are in sorted order.

Termination:
• After k=n-1 runs: A[1]..A[n-1] are all small numbers and sorted, A[n] is the only remaining big

number. Therefore, the whole array is sorted.

small numbers (sorted)
A[1] A[k-1] A[k] A[n]

big numbers (unsorted)

small numbers (sorted)
A[1] A[k] A[k+1] A[n]

big numbers (unsorted)

37Appendix B
Time Complexity
and Correctness

Minsort: Time analysis (1/3)

1.
2.
3.
4.
5.
6.
7.
8.
9.

Time analysis:
To determine how long an algorithm takes
to sort an array: Time

Minsort

38Appendix B
Time Complexity
and Correctness

Minsort: Time analysis (2/3)

Minsort

For each value of k, compare
(n-k) pairs of elements:
(n-1) + (n-2) + … + (1) =
n(n-1)/2

1.
2.
3.
4.
5.
6.
7.
8.
9.

Time analysis:
To determine how long an algorithm takes
to sort an array, we typically measure the
number of comparisons of array entries.

39Appendix B
Time Complexity
and Correctness

Minsort: Time analysis (3/3)

Minsort

1.
2.
3.
4.
5.
6.
7.
8.
9.

Time analysis:
To determine how long an algorithm takes
to sort an array, we typically measure the
number of comparisons of array entries.

For Minsort, what is the maximum number
of times we might have to compare the
values of a pair of array elements?
‐Worst Case
‐ Best Case
‐ Average Case

40Appendix B
Time Complexity
and Correctness

Running time analysis for Minsort: Upper Bound

MinSort(a1, a2, …, an: real numbers with n>=2 )
1 for i := 1 to n-1
2 m := i
3 for j:= i+1 to n
4 if ( aj < am ) then m := j 5 interchange ai and am O(1) O(n-i) = O(n) O(1) Simple Loop Basic Operation Basic Operation Nested Loop, repeats O(n) times We work from the inside out, going from the body of the inside loop to the main algorithm. • The inner-most Line 4 is defined in terms of a fixed number of basic operations: 1 comparison and at most 1 assignment. It is thus O(1). • Line 3 is a loop, with constant time line 4 inside. It repeats n-i times, and this ranges from 1 comparison (when j=n (i=n-1)) to n-1 comparisons when j=2 (i=1). So the worst-case is O(n). • Line 2 and 5 are constant time, so the body of the FOR loop in line 1 takes O(1+n+1) = O(n) total. • Line 1 is a loop whose body is O(n) and gets repeated n-1 times. • So the whole algorithm is O(n2). 41Appendix B Time Complexity and Correctness Running time analysis for Minsort: Lower Bound O is an upper bound, not always tight. Is the running time also lower bounded by a quadratic, or is there a smaller upper bound? We don't need to find the “worst-case input” or give an exact formula to answer this question, just show that the Minsort needs at least n2) comparisons: • Look at the first n/2 times we run the loop in line 3. Then i < n/2, so n-i > n/2.

• Thus, we run it at least n/2 x n/2 = n2/4 times total.
This is (n2).

• Thus, the time is both O(n2) and (n2), so our analysis
is tight, and the time is (n2).

MinSort(a1, a2, …, an: real numbers with n>=2 )
1 for i := 1 to n-1
2 m := i
3 for j:= i+1 to n
4 if ( aj < am ) then m := j 5 interchange ai and am O(1) O(n-i) = O(n) O(1) Simple Loop Basic Operation Basic Operation Nested Loop, repeats O(n) times 42Appendix B Time Complexity and Correctness Iterative algorithms 2 Bubble Sort 43Appendix B Time Complexity and Correctness Bubble Sort Idea: Compare the first two numbers, and if the first is bigger, keep comparing it to the next number in the array until we find a larger one. Repeat until the array is sorted. A[1] A[2] A[3] A[4] k=1 49 29 3 25 29 49 3 25 29 3 49 25 29 3 25 49 k=2 29 3 25 3 29 25 3 25 29 k=3 3 25 Bubble Sort Begin. 1. for k := 1 to n-1 2. for j := 1 to n-k 3. if A[j] > A[j+1] then
4. interchange A[j] and A[j+1]
End.

Exercise:
• Find a loop invariant that implies correctness.
• Prove the loop invariant.

44Appendix B
Time Complexity
and Correctness

Bubble Sort: Correctness (1/2)

Loop Invariant: After the kth iteration through the outer for-loop, the last k positions A[n-k+1] .. A[n]
contain the k largest array elements in sorted order.

We distinguish between small numbers (all unsorted) and big numbers (all sorted).
All big numbers are > to all small numbers.

Induction Base (k=0): Before we enter the outer for-loop for the first time,
all numbers are small numbers, i.e. unsorted.

Induction Hypothesis: Same as Loop Invariant for iteration k-1.

small numbers (unsorted)
A[1] A[n]

small numbers (unsorted)
A[1] A[n-k+1)] A[n-k+2] A[n]

big numbers (sorted)

45Appendix B
Time Complexity
and Correctness

Bubble Sort: Correctness (2/2)

Induction Step:
• Inner for-loop (lines 2-4): compare the numbers at positions

(1, 2), (2, 3), …, (n-k, n-k+1) and interchange these so that
always the larger element of a pair ends up further to the right.

• As a result, A[n-k+1] contains the largest number (let’s call it max)
of the first n-k+1 numbers.

• max is the largest of the small numbers and therefore > to all small
numbers, max is < all big numbers as all small numbers are < all big numbers. • The set of small numbers has been decreased by 1 and the set of big numbers has been increased by 1. With the help of the Induction Hypothesis, now the last k numbers A[n-k+1..n] are in sorted order. Termination: • After k=n-1 runs: A[2]..A[n] are all big numbers and sorted, A[1] is the only remaining small number. Therefore, the whole array is sorted. small numbers (unsorted) A[1] A[n-k] A[n-k+1] A[n] big numbers (sorted) small numbers (unsorted) A[1] A[n-k+1] A[n-k+2] A[n] big numbers (sorted) A[1] A[2] A[n-k+1] Bubble Sort Begin. 1. for k := 1 to n-1 2. for j := 1 to n-k 3. if A[j] > A[j+1] then
4. interchange A[j] and A[j+1]
End.

46Appendix B
Time Complexity
and Correctness

Iterative algorithms 3

Insertion Sort

47Appendix B
Time Complexity
and Correctness

Insertion Sort

Idea: Take an element of A and find where it belongs relative to the elements before it.
Shift everything back to make room and put the element in its proper place. Now that
this element has been inserted where it belongs, do the same for the next element of A.

A[1] A[2] A[3] A[4]
49 29 3 25

j=2 29 49 3 25
j=3 3 29 49 25
j=4 3 25 29 49

Insertion Sort
Begin.
1. for j:=2 to n
2. m:=A[j];
3. i:=1;
4. while m>A[i]
5. i:=i+1;
6. for k:=0 to j-i-1
7. A[j-k]:=A[j-k-1];
8. A[i]:=m;
End.

48Appendix B
Time Complexity
and Correctness

Insertion Sort: Correctness (1/2)

Loop Invariant: After the lth iteration through the outer for-loop, the first l+1 positions A[1] .. A[l+1]
are sorted with respect to the first l+1 elements of the input.

Induction Base (l=0): Before we enter the outer for-loop for the first time, only the first number is
sorted with respect to the first element of the original array. All other numbers are unsorted.

Induction Hypothesis: Same as Loop Invariant for iteration l-1.

sorted wrt the first l elements of the input

A[1] A[l] A[l+1] A[n]
unsorted numbers

unsorted numbers
A[1] A[n]A[2]

49Appendix B
Time Complexity
and Correctness

Insertion Sort: Correctness (2/2)

Induction Step:
• During the l-th run through the outer for-loop, the number m at position l+1

is moved to its correct position among the first l+1 elements of the original
array.

• Line 2: m is that element of the original array that has to be inserted in the
sorted list.

• Lines 3..5: Find the correct position i for m among the first l elements of
the original array. The while loop executes until either i=j (in this case we
would have m=A[i]) or it encounters the first i < j such that m < A[i]. • Lines 6..7: Shift the elements A[i] .. A[j-1] one position to the right. • Line 8: Insert m at position A[i]. • The set of unsorted numbers has been decreased by 1 and the set of sorted numbers with respect to the first elements of the input has been increased by 1. With the help of the Induction Hypothesis, now the first l+1 numbers A[1..l+1] are in sorted order. Termination: • After n-1 runs: A[1]..A[n] are all sorted, i.e. the whole array is sorted. sorted wrt the first l elements of the input A[1] A[l] A[l+1] A[n] unsorted numbers sorted wrt the first l elements of the input A[1] A[l+1] A[n] unsorted numbers A[l+2] Insertion Sort Begin. 1. for j:=2 to n 2. m:=A[j]; 3. i:=1; 4. while m>A[i]
5. i:=i+1;
6. for k:=0 to j-i-1
7. A[j-k]:=A[j-k-1];
8. A[i]:=m;
End.

50Appendix B
Time Complexity
and Correctness

Iterative algorithms 4

Linear Search

51Appendix B
Time Complexity
and Correctness

Searching

Given an array
A[1], A[2], A[3], …, A[n]

and a target value
x,

find an index j where x = A[j] or
determine that no such index exists
because x is not in the array.

Example:
Input: A[1]=2, A[2]=529, A[3]=0, A[4]=1, x=529

Output: j=?

52Appendix B
Time Complexity
and Correctness

Linear Search

Idea:
• Search through the array one index at a time, asking “Is this my target value?” at each

position.
• If you answer yes, return the position where you found it.
• Otherwise, return 0.

Linear Search is correct, i.e. the algorithm returns the first location k of the target value x
in the array, or 0 if the target is not present in the array.

Exercise:
• Find a loop invariant that implies correctness.
• Prove the loop invariant.

1 for (k=1..n)
2 if (A[k]==x) return k;
3 return 0;

53Appendix B
Time Complexity
and Correctness

Linear Search: Correctness

Loop invariant: After the kth run through the for‐loop,
Linear Search will
‐ either return a nonzero position k (if A[k]=x), or
‐ continue to the next loop iteration (if A[k]!=x and k<=n‐1). If Linear Search returns 0, then there is no position k for which A[k]=x. Induction Base (k=0): Before we enter the for‐loop, clearly x has not been detected. Induction Hypothesis: Same as Loop Invariant for iteration k‐1. Induction Step: If there is a kth run through the for‐loop, the element has not been detected during the first k‐1 runs through the for‐loop (Induction Hypothesis). Line 2: During the kth run, either A[k]=x and the algorithm returns k, or not, and the loop continues (if k<=n‐1) or ends (if k=n). Termination: If k=n and A[n] is not equal to x, the algorithm returns 0. In all other cases, the element x has been detected and the algorithm returns the correct position. Note: This example is special and we have to do a case distinction because we can break out of the for‐loop. Such a break out is not the regular case! 1 for (k=1..n) 2 if (A[k]==x) return k; 3 return 0; 54Appendix B Time Complexity and Correctness Linear Search: Time analysis (1/2) Exercise: Suppose you have an unsorted array and you are searching for a target value x that you know is in the array somewhere. What position for x will cause linear search to take the longest amount of time? A) x is the first element of the array B) x is the last element of the array C) x is somewhere in the middle of the array 55Appendix B Time Complexity and Correctness Linear Search: Time analysis (2/2) Exercise: Suppose you have an unsorted array and you are searching for a target value x that you know is in the array somewhere. What position for x will cause linear search to take the longest amount of time? A) x is the first element of the array B) x is the last element of the array C) x is somewhere in the middle of the array Say our array A has n elements and we are searching for x. The time it takes to find x (or determine it is not present) depends on the number of probes, that is the number of entries we have to retrieve and compare to x. How many probes? Worst case scenario: Best case scenario: On average: 56Appendix B Time Complexity and Correctness Linear Search: Time analysis (2/2) Exercise: Suppose you have an unsorted array and you are searching for a target value x that you know is in the array somewhere. What position for x will cause linear search to take the longest amount of time? A) x is the first element of the array B) x is the last element of the array C) x is somewhere in the middle of the array Say our array A has n elements and we are searching for x. The time it takes to find x (or determine it is not present) depends on the number of probes, that is the number of entries we have to retrieve and compare to x. How many probes? Worst case scenario: The target is the last element in the n probes array or not present at all. Best case scenario: The target is the first element in the 1 probe array. On average: We'd expect to have to search about about n/2 probes half of the array until we find the target. 57Appendix B Time Complexity and Correctness Iterative algorithms 5 Binary Search 58Appendix B Time Complexity and Correctness Binary Search (1/2) Exercise: How would you search through a pile of alphabetized papers to find the one with your name on it? Suppose we probe A at position m. What do we learn? If x=A[m], we are done. If xA[m], then if x is in the array, its position is after m.

n‐m positions remain to be checked

If our array has 100 elements and we probe at position 5, it is most likely that the target is
in the second half, so we’ll have to search 95 entries in the worst case.

How do we make the worst case as favorable as possible? Probe in the middle.
If we are searching the subarray A[i], …, A[j], probe at index

59Appendix B
Time Complexity
and Correctness

Binary Search (2/2)

Idea: Probe in the middle of the array. Based on what you find there, determine which
half to search in next. Continue until the target is found or you can be sure the target is
not in the array. Return the location of the target, or 0 if the target is not in the array.

int BinarySearch(int A[1..n] (a sorted integer array), int x)
1. i:=1;
2. j:=n;
3. while (i < j) 4. m := (i+j) / 2; 5. if (x = A[m]) return m; 6. if (x > A[m]) i:=m+1;
7. if (x < A[m]) j:=m-1; 8. return 0; Exercise: • Find a loop invariant that implies correctness. • Prove the loop invariant. 60Appendix B Time Complexity and Correctness Binary Search: Correctness Loop invariant: After the kth run through the while‐loop, either Binary Search will ‐ either return a nonzero position m (A[m]=x and i A[m], i is
increased to i=m+1 (all elements at positions with a smaller index must be smaller than
x). If x A[m]) i:=m+1;
7. if (x < A[m]) j:=m-1; 8. return 0; 61Appendix B Time Complexity and Correctness Binary Search: Time analysis With each comparison, we reduce the size of the subarray we are searching to at most half of its previous size. How many comparisons w do we need to make sure our search has terminated? That is, what value of w is sure to make the subarray size less than or equal to 1? 62Appendix B Time Complexity and Correctness Linear Search vs. Binary Search Linear Search Binary Search Best Case 1 1 Worst Case n Average Case (n+1) / 2 If Binary Search is really faster than Linear Search depends upon the array being sorted. When we are lucky enough, Linear Search might just use 1 comparison, whereas Binary Search could use as many as about log n comparisons for a certain input. What is the worst‐case number of comparisons if we look for several elements in the array? Note that we have to sort at first the array when we want to use Binary Search. we search for ... Linear Search Binary Search ... 1 element O(n) O(n log n) + O(log n) = O(n log n) ... n elements O(n2) O(n log n) + O(n log n) = O(n log n) ... n2 elements O(n3) O(n log n) + O(n2 log n) = O(n2 log n) 63Appendix B Time Complexity and Correctness Iterative algorithms 6 Summing Triple 64Appendix B Time Complexity and Correctness How O distinguishes between major and incremental improvements At this point, we have seen ‐ the Definition of O and related order notations, and have seen ‐ some simple ways of using the properties of O to analyze the time of algorithms up to order. Next, we'll look at how we can use order notation to help us design better algorithms. {What is better?} Order notation naturally distinguishes between small improvements in algorithm design and major gains. 65Appendix B Time Complexity and Correctness Summing Triple Input: An array A[1,…,n] of integers. Summing Triple: A Summing Triple is a list of three indices 1 < i, j, k < n so that A[i] + A[j] = A[k]. Problem: Is there a Summing Triple? Example: A[1,2,3,4] = [3,-6,5,8]. A[1] + A[3] = A[4]  1, 3, 4 are a Summing Triple. 66Appendix B Time Complexity and Correctness Summing Triple: Most obvious algorithm („Brute‐Force“) A[1,2,3,4] = [3,-6,5,8]. A[1] + A[3] = A[4]  1, 3, 4 are a Summing Triple. SummingTriple(A[1..n]) 1 for(i:=1..n) 2 { 3 for(j:=1..n) 4 { 5 for(k:=1..n) 6 { 7 if(A[i]+A[j] == A[k]) return(true); 8 } // for(k:=1..n) 9 } // for(j:=1..n) 10 } // for(i:=1..n) 11 return(false); 67Appendix B Time Complexity and Correctness Summing Triple: Time analysis of the Brute‐Force‐algorithm A[1,2,3,4] = [3,-6,5,8]. A[1] + A[3] = A[4]  1, 3, 4 are a Summing Triple. SummingTriple(A[1..n]) 1 for(i:=1..n) 2 { 3 for(j:=1..n) 4 { 5 for(k:=1..n) 6 { 7 if(A[i]+A[j] == A[k]) return(true); 8 } // for(k:=1..n) 9 } // for(j:=1..n) 10 } // for(i:=1..n) 11 return(false); 3 Nested Loops, each makes maximal n iterations, so n3 total operations. Therefore, T(n) O(n3) (n3 exactly) 68Appendix B Time Complexity and Correctness Summing Triple: Eliminating some redundancy A[1,2,3,4] = [3,-6,5,8]. A[1] + A[3] = A[4]  1, 3, 4 are a Summing Triple. SummingTriple(A[1..n]) 1 for(i:=1..n) 2 { 3 for(j:=i..n) 4 { 5 for(k:=1..n) 6 { 7 if(A[i]+A[j] == A[k]) return(true); 8 } // for(k:=1..n) 9 } // for(j:=i..n) 10 } // for(i:=1..n) 11 return(false); We checked every i and j twice, in both orders. That‘s too much as e.g. A[1]+A[3]=A[3]+A[1]. This new algorithm has eliminated about half of the work of the previous one. But a constant factor of 1/2 does not change the order, so we still have: T(n) O(n3) ((n3+n2)/2 exactly) 69Appendix B Time Complexity and Correctness Summing Triple: Tightness of the bound A[1,2,3,4] = [3,-6,5,8]. A[1] + A[3] = A[4]  1, 3, 4 are a Summing Triple. SummingTriple(A[1..n]) 1 for(i:=1..n) 2 { 3 for(j:=i..n) 4 { 5 for(k:=1..n) 6 { 7 if(A[i]+A[j] == A[k]) return(true); 8 } // for(k:=1..n) 9 } // for(j:=i..n) 10 } // for(i:=1..n) 11 return(false); The innermost k-loop takes n steps, and inside we take at least some constant time 1), so the inside loop takes (n) time each time. 70Appendix B Time Complexity and Correctness Summing Triple: Tightness of the bound A[1,2,3,4] = [3,-6,5,8]. A[1] + A[3] = A[4]  1, 3, 4 are a Summing Triple. SummingTriple(A[1..n]) 1 for(i:=1..n) 2 { 3 for(j:=i..n) 4 { 5 for(k:=1..n) 6 { 7 if(A[i]+A[j] == A[k]) return(true); 8 } // for(k:=1..n) 9 } // for(j:=i..n) 10 } // for(i:=1..n) 11 return(false); The innermost k-loop takes n steps, and inside we take at least some constant time 1), so the inside loop takes (n) time each time. The number of times we go through the j-loop depends on i . But there are n/2 times (when i= 1..n/2) when we go through the j-loop at least n/2 times. That means the inside k-loop is executed at least n/2 x n/2 = n2/4 times, and each time it takes (n). Thus the total time is (n3). 71Appendix B Time Complexity and Correctness Summing Triple: Tightness of the bound A[1,2,3,4] = [3,-6,5,8]. A[1] + A[3] = A[4]  1, 3, 4 are a Summing Triple. SummingTriple(A[1..n]) 1 for(i:=1..n) 2 { 3 for(j:=i..n) 4 { 5 for(k:=1..n) 6 { 7 if(A[i]+A[j] == A[k]) return(true); 8 } // for(k:=1..n) 9 } // for(j:=i..n) 10 } // for(i:=1..n) 11 return(false); The innermost k-loop takes n steps, and inside we take at least some constant time 1), so the inside loop takes (n) time each time. The number of times we go through the j-loop depends on i . But there are n/2 times (when i= 1..n/2) when we go through the j-loop at least n/2 times. That means the inside k-loop is executed at least n/2 x n/2 = n2/4 times, and each time it takes (n). Thus the total time is (n3). Since this algorithm is both O(n3) and (n3), its time is (n3). Our original analysis was tight. 72Appendix B Time Complexity and Correctness Summing Triple: Linear Search SortedSummingTriple(A[1..n]: sorted array of integers) 1 for(i:=1..n) 2 { 3 for(j:=i..n) 4 { 5 if (LinearSearch(A,A[i]+A[j])) return(true); 6 } // for(j:=i..n) 7 } // for(i:=1..n) 8 return(false); We can use Linear Search to see if A[i] + A[j] is in the array A[1..n]. It doesn't change the algorithm, but this different viewpoint suggests a possibility for improvement. Since Linear Search takes (n) time, and we have two nested loops with at most n iterations each, the total time is (n3). A[1,2,3,4] = [-6,3,5,8]. A[2] + A[3] = A[4]  2, 3, 4 are a Summing Triple. 73Appendix B Time Complexity and Correctness Summing Triple: Binary Search SortedSummingTriple(A[1..n]: sorted array of integers) 1 for(i:=1..n) 2 { 3 for(j:=i..n) 4 { 5 if (BinarySearch(A,A[i]+A[j]) return(true); 6 } // for(j:=i..n) 7 } // for(i:=1..n) 8 return(false); Since Binary Search takes (log n) time, and we have two nested loops with at most n iterations each, the total time is (n2 log n). A[1,2,3,4] = [-6,3,5,8]. A[2] + A[3] = A[4]  2, 3, 4 are a Summing Triple. 74Appendix B Time Complexity and Correctness Summing Triple: Time analysis SummingTriple (A[1..n]: array of integers) 1 Bubblesort(A);  (n2) 2 return(SortedSummingTriple(A));  (n2 log n)  (n2 + n2 log n) = (n2 log n) “<“ n3) Remarks: • this is an asymptotically strictly better algorithm than what we started with • an asymptotically faster sorting procedure will not improve the asymptotic running time • the currently best algorithms for Summing Triple take (n2) time • the question of whether there is a better algorithm than (n2) is unknown and subject of active research We cannot assume the array A is sorted, but we can ensure that it is sorted. 75Appendix B Time Complexity and Correctness Iterative algorithms 7 Intersection 76Appendix B Time Complexity and Correctness Intersection problem Given two sorted arrays A[1..n] and B[1..n], determine if they intersect, i.e. if there are i, j, such that A[i] = B[j]. Intersect(A[1..n], B[1..n]) 1 i:=1; 2 for(j:=1..n) 3 { 4 while(B[j] > A[i] and i < n) i++; 5 if( i > n ) return(false);
6 if( B[j] == A[i] ) return(true);
7 }
8 return(false);

A: 1 2 5 A: 3 4 5
B: 3 4 5 B: 1 2 5
3 > 1? yes 1 > 3? no
3 > 2? yes 2 > 3? no
3 > 5? no 5 > 3? yes
4 > 5? no 5 > 4? yes
5 > 5? no 5 > 5? no
5 = 5? yes 5 = 5? yes

77Appendix B
Time Complexity
and Correctness

Intersection problem

Given two sorted arrays A[1..n] and B[1..n],
determine if they intersect, i.e. if there are i, j,
such that A[i] = B[j].
Intersect(A[1..n], B[1..n])
1 i:=1;
2 for(j:=1..n)
3 {
4 while(B[j] > A[i] and i < n) i++; 5 if( i > n ) return(false);
6 if( B[j] == A[i] ) return(true);
7 }
8 return(false);

In the worst-case, the inside while-loop can
run n times, and the outside for-loop has n
iterations.

Thus, we have an upper bound of O(n2) time.

A: 1 2 5 A: 3 4 5
B: 3 4 5 B: 1 2 5
3 > 1? yes 1 > 3? no
3 > 2? yes 2 > 3? no
3 > 5? no 5 > 3? yes
4 > 5? no 5 > 4? yes
5 > 5? no 5 > 5? no
5 = 5? yes 5 = 5? yes

What is the lower bound?
(n)

78Appendix B
Time Complexity
and Correctness

Intersection problem

A: 1 2 5 A: 3 4 5
B: 3 4 5 B: 1 2 5
3 > 1? yes 1 > 3? no
3 > 2? yes 2 > 3? no
3 > 5? no 5 > 3? yes
4 > 5? no 5 > 4? yes
5 > 5? no 5 > 5? no
5 = 5? yes 5 = 5? yes

In the worst-case, the inside while-loop can
run n times, and the outside for-loop has n
iterations.

Thus, we have an upper bound of O(n2) time.

Since B[j] > B[j-1], we can start the search for the
next B[j] where our search for B[j-1] left off. And
since A[i] > A[i-1], we can start the search for the
next A[i] where our search for A[i-1] left off.

The inside while-loop can run at most n times in total
but after that it won’t be done at all:
If i reaches n+1, the algorithm terminates and returns
false (Line 5).
The algorithm terminates as well when j reaches n+1
and returns false in this case (Line 8).
And it terminates as soon as some B[j]=A[i] (Line 6).
The tight running time is therefore (n).

79Appendix B
Time Complexity
and Correctness

Recursive algorithms 1

Exponentiation

80Appendix B
Time Complexity
and Correctness

Example: Exponentiation (Correctness Proof)

The following algorithm, given a positive integer n, computes 2n.
int ExpBase2(int n)
if(n==1) then return(2);
return(ExpBase2(n-1) * 2);

81Appendix B
Time Complexity
and Correctness

Example: Exponentiation (Correctness Proof)

The following algorithm, given a positive integer n, computes 2n.
int ExpBase2(int n)
if(n==1) then return(2);
return(ExpBase2(n-1) * 2);

C
or

re
ct

ne
ss

Proof (by induction on n): ExpBase2(n) returns 2n.

• Base Case (n=1): When n=1, then the algorithm returns 2=21.

• Induction Hypothesis: Assume that ExpBase2(n-1) returns 2n-1 for n > 1.

• Induction Step (n-1n): ExpBase2(n) returns
ExpBase2(n-1)*2 = 2n–1 * 2 = 2n.

82Appendix B
Time Complexity
and Correctness

Example: Exponentiation (Time analysis)

Let M(n) be the number of multiplications needed to compute 2n with ExpBase2.

Time analysis strategy 1: “Guess and Check, then Induction”

M(1)=0
M(2)=1
M(3)=2
M(4)=3
…
M(n)=???

Ti
m

e
an

al
ys

isThe following algorithm, given a positive integer n, computes 2
n.

int ExpBase2(int n)
if(n==1) then return(2);
return(ExpBase2(n-1) * 2);

83Appendix B
Time Complexity
and Correctness

Example: Exponentiation (Time analysis)

Let M(n) be the number of multiplications needed to compute 2n with ExpBase2.

Time analysis strategy 1: “Guess and Check, then Induction”

M(1)=0
M(2)=1
M(3)=2
M(4)=3
…
M(n)=n-1

Ti
m

e
an

al
ys

isThe following algorithm, given a positive integer n, computes 2
n.

int ExpBase2(int n)
if(n==1) then return(2);
return(ExpBase2(n-1) * 2);

84Appendix B
Time Complexity
and Correctness

Example: Exponentiation (Time analysis)

Let M(n) be the number of multiplications needed to compute 2n with ExpBase2.

Time analysis strategy 1: “Guess and Check, then Induction”

M(1)=0
M(2)=1
M(3)=2
M(4)=3
…
M(n)=n-1

Ti
m

e
an

al
ys

isThe following algorithm, given a positive integer n, computes 2
n.

int ExpBase2(int n)
if(n==1) then return(2);
return(ExpBase2(n-1) * 2);

Proof (by induction): ExpBase2(n) needs n-1 multiplications to compute 2n.

Base Case (n=1): 0 multiplications to compute 21=2.
Induction Hypothesis: n-2 multiplications to compute 2n-1.
Induction Step (n-1n): 2n = 2n–1 * 2, we need therefore n-2 + 1 = n-1
multiplications with 2 to compute 2n.

85Appendix B
Time Complexity
and Correctness

Example: Exponentiation (Time analysis)

Let M(n) be the number of multiplications needed to compute 2n with ExpBase2.

Time analysis strategy 2: “Unraveling the recurrence”

M(1) = 0
M(n) = M(n-1)+1

Ti
m

e
an

al
ys

isThe following algorithm, given a positive integer n, computes 2
n.

int ExpBase2(int n)
if(n==1) then return(2);
return(ExpBase2(n-1) * 2);

86Appendix B
Time Complexity
and Correctness

Example: Exponentiation (Time analysis)

Let M(n) be the number of multiplications needed to compute 2n with ExpBase2.

Time analysis strategy 2: “Unraveling the recurrence”

M(1) = 0
M(n) = M(n-1)+1

= M(n-2)+2
= …
= M(1)+n-1 = n-1

Ti
m

e
an

al
ys

isThe following algorithm, given a positive integer n, computes 2
n.

int ExpBase2(int n)
if(n==1) then return(2);
return(ExpBase2(n-1) * 2);

87Appendix B
Time Complexity
and Correctness

Recursive algorithms 2

Merging sorted arrays

88Appendix B
Time Complexity
and Correctness

Merging sorted arrays

89Appendix B
Time Complexity
and Correctness

Iterative Merge: Correctness

C
or

re
ct

ne
ssImerge(A[1..k], B[1..l]: sorted arrays)

1 n:=k+l; i:=1; j:=1;
2 for(t:=1..n)
3 if(i > k) then C[t]:=B[j++];
4 if(j > l) then C[t]:=A[i++];
5 if(A[i] <= B[j] ) 6 then C[t]:=A[i++]; 7 else C[t]:=B[j++]; Loop Invariant: After t iterations, C[1..t] contains the t smallest elements from A[1..i-1] and B[1..j-1] in sorted order. for-loop: There are exactly n assignments C[1..n] (n) Ti m e an al ys is 90Appendix B Time Complexity and Correctness Recursive Merge Rmerge(A[1..k], B[1..l]: sorted arrays) 1 if(k == 0) then return(B[1..l]); 2 if(l == 0) then return(A[1..k]); 3 if(A[1] <= B[1] ) 4 then return A[1] o Rmerge(A[2..k],B[1..l]); 5 else return B[1] o Rmerge(A[1..k],B[2..l]); 91Appendix B Time Complexity and Correctness Recursive Merge Rmerge(A[1..k], B[1..l]: sorted arrays) 1 if(k == 0) then return(B[1..l]); 2 if(l == 0) then return(A[1..k]); 3 if(A[1] <= B[1] ) 4 then return A[1] o Rmerge(A[2..k],B[1..l]); 5 else return B[1] o Rmerge(A[1..k],B[2..l]); C or re ct ne ss 92Appendix B Time Complexity and Correctness Recursive Merge Rmerge(A[1..k], B[1..l]: sorted arrays) 1 if(k == 0) then return(B[1..l]); 2 if(l == 0) then return(A[1..k]); 3 if(A[1] <= B[1] ) 4 then return A[1] o Rmerge(A[2..k],B[1..l]); 5 else return B[1] o Rmerge(A[1..k],B[2..l]); C or re ct ne ss Proof (by induction on n=k+l): Rmerge(A[1..k], B[1..l]) returns a sorted array containing all n=k+l elements from either array. • Base Case (n=1): When n=1, then either k=0 or l=0, and the algorithm returns either the sorted array B[1..l] (if k=0) or the sorted array A[1..k] (if l=0). • Induction Hypothesis: Assume that Rmerge(A[2..k], B[1..l]) and Rmerge(A[1..k], B[2..l]) each return a sorted array containing all elements from either array. • Induction Step (n-1n): Case 1: A[1] <= B[1]. Then Rmerge(A[1..k], B[1..l]) returns a sorted array containing all n=k+l elements from either array: A[1] is the smallest element of all elements and (by the Induction Hypothesis) Rmerge(A[2..k], B[1..l]) returns a sorted array. Case 2: B[1] < A[1]. Then Rmerge(A[1..k], B[1..l]) returns a sorted array containing all n=k+l elements from either array: B[1] is the smallest element of all elements and (by the Induction Hypothesis) Rmerge(A[1..k], B[2..l]) returns a sorted array. 93Appendix B Time Complexity and Correctness Recursive Merge: Time analysis Ti m e an al ys is Rmerge(A[1..k], B[1..l]: sorted arrays) 1 if(k == 0) then return(B[1..l]); 2 if(l == 0) then return(A[1..k]); 3 if(A[1] <= B[1] ) 4 then return A[1] o Rmerge(A[2..k],B[1..l]); 5 else return B[1] o Rmerge(A[1..k],B[2..l]); Let T(n) be the number of comparisons between two elements of A and B needed to merge the two arrays. Time analysis strategy 1: “Guess and Check, then Induction” Time analysis strategy 2: “Unraveling the recurrence” 94Appendix B Time Complexity and Correctness Recursive Merge: Time analysis Ti m e an al ys is Rmerge(A[1..k], B[1..l]: sorted arrays) 1 if(k == 0) then return(B[1..l]); 2 if(l == 0) then return(A[1..k]); 3 if(A[1] <= B[1] ) 4 then return A[1] o Rmerge(A[2..k],B[1..l]); 5 else return B[1] o Rmerge(A[1..k],B[2..l]); Let T(n) be the number of comparisons between two elements of A and B needed to merge the two arrays. Time analysis strategy 1: “Guess and Check, then Induction” T(1)=0 T(2)=1 T(3)=2 … T(n)=n-1 Proof (by induction): RMerge(A[1..k], B[1..l]) needs n-1 comparisons between two elements of A and B to merge the two arrays. Base Case (n=1): 0 comparisons. Induction Hypothesis: n-2 comparisons. Induction Step (n-1n): Given that Rmerge(A[1..k], B[1..l]) or Rmerge(A[2..k], B[1..l]) need n-2 comparisons between two elements of A and B to merge the two arrays, we need one more comparison to find the smallest of all elements (in line 3). Therefore, we need in total n-1 comparisons. 95Appendix B Time Complexity and Correctness Recursive Merge: Time analysis Ti m e an al ys is Rmerge(A[1..k], B[1..l]: sorted arrays) 1 if(k == 0) then return(B[1..l]); 2 if(l == 0) then return(A[1..k]); 3 if(A[1] <= B[1] ) 4 then return A[1] o Rmerge(A[2..k],B[1..l]); 5 else return B[1] o Rmerge(A[1..k],B[2..l]); Let T(n) be the number of comparisons between two elements of A and B needed to merge the two arrays. Time analysis strategy 2: “Unraveling the recurrence” T(1) = 0 T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(1) + (n-1) = n-1

Related Posts