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

what is market

what is the nearest ten thousand of 92,892?


find the value of 0 that makes cos 21 degrees = sin 0 statement true.

Two circles touch each other externally: Given: Two circles with respective centres C1 and C2 touch each other externaly at the point P. T is any point on the common tangent

how to solve the problems? methods to solve the question of joint lines

Logarithm Functions : Now let's briefly get the derivatives for logarithms.  In this case we will have to start with the following fact regarding functions that are inverses of ea

Prime number A prime number is a number whose only +ve factors are 1 and itself. For instance 2, 3, 5, and 7 are all of the examples of prime numbers.  Examples of numbers whic

Find out if the following series is convergent or divergent. Solution There really is not very much to these problems another than calculating the limit and then usin