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 are some of the interestingmodern developments in cruise control systems that contrast with comparatively basic old systems

Q. What are Mutually Exclusive events? Mutually Exclusive Events are mutually exclusive if they cannot occur at the same time. For example, if you roll one die, you canno

#question.help.

what is the difference between North America''s part of the total population and Africa''s part



what is the derivatives of y=u/5+7 and u=5x-35 using the chain rule?

i need a step by step guide to answering simultaneous equation for gcses

i don''t understand what my teacher when she talks about when she talks about cosecutive integers etc... so can u help me???

my daughter brought home home work im not sure how to do it the fractions has to be labled from least to greatest