Study Guides (248,617)
CSC165H1 (27)

# Summer.2012.e8_solutions.pdf

2 Pages
124 Views

Department
Computer Science
Course Code
CSC165H1
Professor
Nathalie Fournier

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

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

Unlock Document

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.