Prove asymptotic bounds for recursion relations, Mathematics

Assignment Help:

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.


Related Discussions:- Prove asymptotic bounds for recursion relations

The quotient of 3d3 and 9d5 is, The quotient of 3d 3 and 9d 5 is The ...

The quotient of 3d 3 and 9d 5 is The key word quotient means division so the problem becomes 1d 3 -5/ 5. Divide the coef?cients:  1d 3 /3d-5 . While dividing like bases, subt

Erin is painting a bathroom what is the area to be painted, Erin is paintin...

Erin is painting a bathroom along with four walls each measuring 8 ft through 5.5 ft. Ignoring the doors or windows, what is the area to be painted? The area of the room is the

Free - undamped vibrations, It is the simplest case which we can consider. ...

It is the simplest case which we can consider. Unforced or free vibrations sense that F(t) = 0 and undamped vibrations implies that g = 0. Under this case the differential equation

Cylinder - three dimensional spaces, Cylinder The below equation is th...

Cylinder The below equation is the common equation of a cylinder. x 2 /a 2 + y 2 /b 2 = 1 This is known as a cylinder whose cross section is an ellipse.  If a = b we

staticis, a statisics professor plans classes so carefully that the length...

a statisics professor plans classes so carefully that the lengths of her classes are uniformly distributed between 46.0 and 56.0 minutes. find the probability that a given class pe

Numbers, use the distributive law to write each multiplication in a differe...

use the distributive law to write each multiplication in a different way. then find the answer. 12x14 16x13 14x18 9x108 12x136 20x147

Index of summation - sequences and series, Index of summation - Sequences a...

Index of summation - Sequences and Series Here now, in the i is termed as the index of summation or just index for short and note that the letter we employ to represent

Prove sum of squares any two sides equal twice square, Prove that in any tr...

Prove that in any triangle the sum of the squares of any two sides is equal to twice the square of half of the third side together with twice the square of the median, which bisect

Price cutter sold 85 beach towels what were the total sales, Price Cutter s...

Price Cutter sold 85 beach towels for $6.95 each. What were the total sales? You must multiply the number of towels sold through the price of each towel; 85 × $6.95 = $590.75.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd