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?

Last modified 10:33:29 CST 05 February 2016 by Ron K. Cytron