## Department of Computer Science and Engineering CSE 247 / 502N Spring 2016 Homework 1: Asymptotic Complexity

### Due: 10 February 2016 at 2:30 PM, turn in Brown 100 in class

You must turn this in on paper in class. Any emailed solutions will be discarded without reply.
1. Problem 3.1-1 on page 52 of the text
Do the proof by showing each of:
• max(f(n),g(n)) = O(f(n)+g(n))
• max(f(n),g(n)) = Ω(f(n)+g(n))
Recall from class you can do this by showing:
• f(n)+g(n) = O(max(f(n),g(n))
2. For each of the following code fragments, compute precise statement counts in terms of n. Show your work, including for each loop how many times its body executes per iteration of the next outermost loop. S1 and S2 represent single constant-time statements.
3. Answer each of the following questions. Justify your answers using either the definitions of O, Ω, and Θ, or the techniques shown in class (along with basic math).

4. In Lecture 4 on slide 50 the fact that ak>0 is used to show that c by construction is also positive. What other assumption could have been made about the ai so that c would be positive?