CSC165H1Y Homework Exercise # 8 Summer 2012
Worth: 3% Due: By 3 pm on Tuesday August 7.
1. The following is one of possible implementation of insertion sort:
# Precondition: A is a list of n numbers and n = len(A)
1. for i in 0, 1, ..., n-1:
2. for j in i-1, i-2, ..., 0:
3. if A[j] < A[j+1]:
4. tmp = A[j]
5. A[j] = A[j+1]
6. A[j+1] = tmp
7. else
8. break
Give a tight bound on the worst-case running time of the above algorithm, and write a detailed proof that
your bound is correct.
2
Let us call the worst-case runtime for the above algorithm W(n). Then W(n) 2 ▯(n ).
This is equivalent to saying that W(n) 2 O(n ) ^ W(n) 2
(n ), so we can prove both parts separately.
W(n) 2 O(n ) () 9c 2 R ;9B 2 N;8n 2 N;n ▯ B ) W(n) ▯ cn 2
Let I be a set of valid inputs to the algorithm. Let t(x) be the time taken by the algorithm on an input x.
(Note: this nomenclature is standard in this course, so it can be used without explicit introduction).
W(n) is the biggest value of t(x) over inputs x of size n.
So, W(n) ▯ cn 2 () 8x 2 I;(size(x) = n) ) t(x) ▯ cn 2
So, we want to prove the following:
+ 2
9c 2 R ;9B 2 N;8n 2 N;n ▯ B ) 8x 2 I;(size(x) = n) ) t(x) ▯ cn
Assume n 2 N and n ▯ 0
Assume A is an array of numbers, and size(A) = n
Then, the outer loop would execute n times.
For each of these executions, the inner loop would execute no more than n times. (usually,
much less, but we only need a bound here)
Each execution of the inner loop would take no more than 5 steps: executing lines 2-6, or
2,7-8.
2 2
So, t(A) ▯ n(1 + 5n) = n + 5n ▯ 6n
Then, 8x 2 I;(size(x) = n) ) t(x) ▯ 6n 2
Then, 8n 2 N;n ▯ 0 ) 8x 2 I;(size(x) = n) ) t(x) ▯ 6n 2
+
# Now, use Existential Introduction, take B = 0, 0 2 N, and c = 6, 6 2 R
Then, 9c 2 R ;9B 2 N;8n 2 N;n ▯ B ) 8x 2 I;(size(x) = n) ) t(x) ▯ cn 2
Then, W(n) 2 O(n ) 2
Note: there are many ways of counting lines for the algorithm. We may or may not count the last execution
of the for loop, the implicit \goto" in the if-statement, etc. Any reasonable and consistent way is ok, and should
give the same bound.
Dept. of Computer Science, Un

More
Less