2 Pages

Computer Science
Course Code
Nathalie Fournier

This preview shows 80% of the first page. Sign up to view the full 2 pages of the document.
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
Unlock Document

Only 80% of the first page are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.