This

**preview**shows half of the first page. to view the full**2 pages of the document.**CS 341, Winter 2010

Timothy Chan

Assignment 1 (due Jan 28 Thursday noon)

Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html ﬁrst for general in-

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) = n√log 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

###### You're Reading a Preview

Unlock to view full version