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
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
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.
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
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: 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)
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.
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)
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.
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. 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.
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)
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
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)
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
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.
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
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
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-1n): 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-1n): 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-1n):
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-1n):
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