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 Risk With decision-making under conditions of risk all possible states of nature are known and the decision maker has sufficient knowledge

How to sovle or prove whether an equation is a identity?

A circular pool is filling along with water. Supposing the water level will be 4 ft deep and the diameter is 20 ft, what is the volume of the water required to fill the pool? (π =

Find out the Greatest Common Factor? The largest number that is a common factor of two numbers (that is, both numbers share the same factor) is called the greatest common facto


A tower and a monument stand on a level plane. the angles of depression on top and bottom of the monument viewed from the top of the tower are 13 degrees and 31 degrees, respective

Multiplication Rule: Dependent Events The joint probability of two events A and B which are dependent is equal to the probability of A multiplied by the probability of B given

i want to work with you, please guide me

I need help with my calculus work

Find models of energy production and energy usage from 2 different countries, each on a different continent, which predict future energy production and demands. How was data collec