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


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
CM and RN are resp. the medians of triangle ABC and Triangle PQR.if triangle ABC similar to Triangle PQR TRIANGLE AMC SIMILAR TO PNR

chapter permutation & combination ex :4.6

factorize the following algebraic expressions

A researcher is investigating the effectiveness of a new medication for lowering blood pressure for individuals with systolic pressure greater than 140. For this population, systol

how do we solve function evaluation f(x)

Solving an equation using Multiplication and Division       A variable is a symbol that represents a number. Usually we use the letters like n , t , or x for variables. For

Write down the system of differential equations for the population of both predators and prey by using the assumptions above. Solution We will start off through letting that

What is Deductive Reasoning ? Geometry is based on a deductive structure -- a system of thought in which conclusions are justified by means of previously assumed or proved sta

Let R be the relation on S = {1, 3, 6, 9, 27} defined by aRb iff a|b. (a) Write down the matrix of R. (b) Draw the digraph of R. (c) Explain whether R is reflexive, irrere

can you tell me how to find the "x" and the "y" when trying to find if two triangles are smiliar