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

Line with rise of five and run of two is positive, Draw a graph which has s...

Draw a graph which has slope of a line with rise of five and run of two is positive.

Complex Numbers, How do you compute the phase/angle of a complex number? i....

How do you compute the phase/angle of a complex number? i.e 1+2i

Homework, How do you simplify 10:30:45

How do you simplify 10:30:45

Help with word problem, You would like to have $4000 in four years for a sp...

You would like to have $4000 in four years for a special vacation following graduation by making deposits at the end of every 6 months in an annuity that pays 7% compounded semiann

Dr.., I need some material on Bachet equation

I need some material on Bachet equation

Ordinary and partial differential equations, A differential equation is ter...

A differential equation is termed as an ordinary differential equation, abbreviated through odes, if this has ordinary derivatives in it. Similarly, a differential equation is term

Laws of set algebra, Laws of Set Algebra From the given Venn diagram w...

Laws of Set Algebra From the given Venn diagram where T is the universal set and A its subset that we can deduce a number of laws as: i. A υ Ø = A ii. A υ T = T

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