Prove asymptotic bounds for recursion relations, Mathematics

1. (‡) Prove asymptotic bounds for the following recursion relations. Tighter bounds will receive more marks. You may use the Master Theorem if it applies.

1. C(n) = 3C(n/2) + n

2. G(n) = G(n - 1) + 1/n

3. I(n) = I(n/2) + n/ lg(n)

2. Define a (p,q)-tree as a rooted tree where every internal node has between p and q (inclusive) children. Use the Master Theorem to give asymptotic bounds for the height of the tree. You can assume both p and q are constants with 2 ≤ p ≤ q.

3. (‡) Dominos

853_domains.png

A 2 × 10 rectangle filled with ten dominos, and a 2 × 2 × 10 box filled with ten slabs.

1. A domino is a 2×1 or 1×2 rectangle. How many different ways are there to completely fill a 2 × n rectangle with n dominos?

2. A slab is a three-dimensional box with dimensions 1 × 2 × 2, 2 × 1 × 2, or 2 × 2 × 1. How many different ways are there to fill a 2 × 2 × n box with n slabs? Set up a recurrence relation and give reasonable exponential upper and lower bounds.

Posted Date: 3/19/2013 5:13:49 AM | Location : United States







Related Discussions:- Prove asymptotic bounds for recursion relations, Assignment Help, Ask Question on Prove asymptotic bounds for recursion relations, Get Answer, Expert's Help, Prove asymptotic bounds for recursion relations Discussions

Write discussion on Prove asymptotic bounds for recursion relations
Your posts are moderated
Related Questions
Decision-Making Under Conditions of Uncertainty With decision making under uncertainty, the decision maker is aware of different possible states of nature, but has insufficient

Assume that the amount of air in a balloon after t hours is specified by                                             V (t ) = t 3 - 6t 2 + 35 Calculate the instantaneous

difference between cpm n pert operation research pdfepted#

It is the last case that we need to take a look at. Throughout this section we will look at solutions to the system, x?' = A x? Here the eigenvalues of the matrix A are compl


prove That J[i] is an euclidean ring

(b) The arity of an operator in propositional logic is the number of propositional variables that it acts on – for example, binary operations (e.g, AND, OR, XOR…) act on two propo

how do you graph y+3=-x+3x on a TI-83 graphing calculator?


Consider two bags, A and B, with the following contents Bag A Bag B 3 white marbles 4 white marbles 2 red marbles