Given the recurrence relation

T(n) = {T(n-1) + 2T(n-2) n >= 3

{11 n = 2

{7 n = 1

a) show that (1) has the solution T(n) = 3 * 2^n - (-1)^n by mathematical induction.

b) Find a simple function f(n) such that T(n) = theta(f(n)). Here simple means the function is of a simple form, e.g. n^3 rather than 5n^3 - 3n+7. Note that you need to prove both upper bound and lower bound.

---

An array has cells numbereed 0,1,...,n. Starting at cell x, you repeatedly flip coins and move up or down, depending on whether you got heads or tails. (X means increasing on a head). The process stopes when you read 0 or n. The random variable Tx denots the number of flips done before you stop.

a) show that there is a number c < 1 for which Pr[Tx > t] = O(c^t). Using this, show that the infinite sum for E[Tx] converges. (hint: how many times could you go in the same direction without stopping?

b) Find a recurrence relation expressing E[Tx+1 in terms of E[Tx] and E[Tx-1] for 0 < x < n. (Hint: if you are at x, then with equal probability your next location is either x-1 or x + 1)

c) Find the general solution to your recurrence from b.

d) Find a particular solution that matches the requirement that E[T0] = E[Tn] = 0. And show E[Tn/2] = Tehta(n^2). This means you need both an upper and lower bound.

---

(Parameters for linear time selection.) Suppose that

T(n) <= T(an) + T(bn) + cn, for large n

Where a,b,c > 0 and a + b < 1. By following induction we can see that T9n) = O(n), which implies there existis a constant C such that T(n) <= Cn for sufficiently large n. Describe the set of constants C we could get from the induction, in terms of a,b,c.

Subject | Mathematics |

Due By (Pacific Time) | 02/10/2015 12:00 pm |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |