Department of Computer Science and Engineering

CSE 247 / 502N

Spring 2016


Homework 2: Recurrence and their solutions

Due: 7 March 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. Text problem 4.3-7 on page 87
    For the recurrence

    T(n) = 4T(n/3) + n

    You are trying to show here that:

    • T(n) = O(nlog34), in other words
    • ∃ c ∃n0 | ∀ n ≥ n0 T(n) ≤ cnlog34
  2. Text problem 4.4-5, page 93


Last modified 17:26:42 CST 29 February 2016 by Ron K. Cytron