Exercise 1                                                 Complexity Classes

1. Briefly explain your answer to the following questions.

• If I prove that an algorithm takes O(n2 ) worst-case-time, is it possible that it takes O(n) on all inputs?

• If I prove that an algorithm takes Θ(n2 ) worst-case-time, is it possible that it takes O(n) on some inputs?

2. True or False?

• Is 2n+1  = O(2n )?

• Is 22n  = O(2n )?

• Is log n = o(nϵ ) for all ϵ > 0?

• Is n = Ω(n)?

• Is log n = O(n−  )?

• Is log 3n  = Θ(log 2n )

• There exists a function f(n) which is in both O(g(n)) and ω(g(n))

• There exists a function f(n) which is in both Θ(g(n)) and o(g(n))

• If f(n) = Θ(g(n)) then limn →∞   = C

Exercise 2                                         Math Refresher: Proof by Induction

1. Use induction to prove 对 i =

2. Use induction to prove 对  = 

Exercise 3                                                      Correctness

Use a loop invariant to prove that the above implementation of BubbleSort is correct. That is, after execution, A[1] ≤ A[2] ≤ · · · ≤ A[A.length].

2. Recall the problem of finding an element in an array A whose value is v, as defined in slide 7 of the Introduction - part 2 lecture slides. Please write pseudocode for linear search, which scans through the array sequentially from the beginning, looking for v . Then use a loop invariant to prove that your algorithm is correct.

Exercise 4                                                       Recurrence