Assignment #1 This is the first assignment from winter 2010 term

47 views2 pages
16 Oct 2011
School
Course

CS 341, Winter 2010
Timothy Chan
Assignment 1 (due Jan 28 Thursday noon)
structions.
1. [4 marks] Give a complete proof from the deﬁnition of ω(not using limits) that
n3.41 2010n1.28 + 1 ω(n3).
2. [12 marks] For each pair of functions f(n) and g(n), ﬁll in the correct asymptotic notation
among Θ, o, and ωin the statement f(n)Ã(g(n)). Formal proofs are not necessary, but
provide brief justiﬁcations for all of your answers. (The default base in logarithms is 2.)
(a) f(n) = (2n)341 + (n+ 350)2010 vs. f(n) = (n+ 341)350 + (3n)2010
(b) f(n) = n1.52nvs. g(n) = n1001.99n
(c) f(n) = nlog nvs. g(n) = nlog n
log log n
(d) f(n) = (log n)log log nvs. g(n) = n0.01
3. [10 marks] Analyze the following pseudocode and give a tight (Θ) bound on the running
time as a function of n. Carefully show your work. (Here, “. . . ” refers to some constant-time
operations that do not change the values of i,j,k,`, and n.)
(a) [5 marks]
1. for i= 1 to ndo {
2. for j= 1 to i+ 3 do
3. for k= 1 to n+ 3 do
4. . . .
5. for j=ito ndo
6. for k=ito ndo
7. for `= 1 to ndo
8. . . .
9. }
1
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Get access

\$10 USD/m
Billed \$120 USD annually
Homework Help
Class Notes
Textbook Notes