-2
votes
1answer
22 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
0
votes
2answers
40 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
37 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
3
votes
2answers
63 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
0
votes
0answers
23 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
2
votes
1answer
69 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
0
votes
3answers
122 views

Prove Upper Bound (Big O) for Fibonacci's Sequence?

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem. We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation ...
1
vote
1answer
70 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
3
votes
1answer
98 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
0
votes
1answer
64 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
0
votes
1answer
32 views

Writing a recurrence in terms of a shift operator

This is a concept that I vaguely understand, but I'd like to get an intuitive understanding of how to write a recurrence relation of the form: $$ t_{n}-3t_{n-1}+2t_{n-2}=0 $$ subject to $$ t_0=2, ...
2
votes
2answers
101 views

Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...
4
votes
4answers
160 views

What sort of math is this, and how would I solve it?

I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
0
votes
3answers
928 views

Master theorem solving

I'm starting to study the master theorem, why does something like $$T(n) = aT(n/b)+f(n)$$ solves to $$f(n)^{\log_ba}$$ ? I'm a bit confused on the resolution
2
votes
2answers
414 views

Analysis of algorithms and recurrence relations

Suppose that the function of the time of execution of some recursive algorithm is given by a recurrence relation of order $n$. Let $$p(x)=0,$$ with $p(x)$ a polynomial of degree $n$, the corresponding ...
2
votes
4answers
209 views

Analysis of Algorithms: Solving Recursion equations: $\quad T(n)= T(cn)+T(dn)+n$

How can I prove that the solution for the following recursion equation is $\Theta(n)$: $$T(n)= T(cn)+T(dn)+n \text{ for } d,c>0 \text{ and } c+d<1$$ Edit: $cn$ on one side only. What I need to ...
3
votes
2answers
284 views

How to solve recurrence relations with emphasis on algorithmic complexity

I am having trouble solving recurrence relations, probably because I am missing the basics. Is there any web reference/book I can read to help me cover the basics? I watched some lectures and read ...
17
votes
4answers
3k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...