0
votes
1answer
13 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
1
vote
1answer
18 views

How can I solve the particular solution of the following recurrence (recursive) relation?

Having $a_n = 3a_{n-1} + 2a_{n-2} + 3·2^{2n-1}$ $a_1 = 12$ $a_0 = 0$ I solved the homogeneous part and got: $a^{{h}}_n = 1/12·2^n - 1/12·1^n$ This is the particular solution that I need to ...
1
vote
0answers
20 views

Using a Recursion Tree to solve the recurrence $T(n) = \sqrt n T(\frac{n}{2}) + 10n$?

I am attempting to solve the above recurence by giving tight $\Theta$ bounds. Assume that the logs here are all base 2! To solve a recursion tree as far as I understand, I need two things. The ...
0
votes
1answer
26 views

Recurrence Relation

So I am just making sure I am on the right track with this. I have the recurrence: T(n) = 2T(n-2) + 1 I am trying to solve this recurrence to get the time complexity T(n) = 2(2T(n-4) + 1) + 1 T(n) ...
0
votes
1answer
28 views

recursive sequence - Which approach can I take to solve this equation?

Having this recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 4·3^n$ $a_1 = 36$ $a_0 = 0$ How can I solve this? I tried by characteristics roots and got stuck: *making $a_n=r^n$ $r^n = 5r^{n-1} - ...
0
votes
1answer
21 views

Tight asymptotic upper and lower bounds

I have a equation: $T(n) = 4T(n/3) + n\ln n$ In this equation, I have to give tight asymptotic upper and lower bounds. What does that mean? I know I can apply Master theorem (which gives me theta ...
0
votes
1answer
24 views

limit of $f_n(a) = a^{f_{n-1}(a)}$ as $n$ approaches infinty for small values of $a$

So a friend started, in boredom, calculating values of what I have formalized as $f_n(a) = a^{f_{n-1}(a)}$ (also $f_0(a)=a$) for $a = 1.1$. He noticed that on his calculator it was not changing value ...
2
votes
1answer
25 views

Recurrence relation of the following sequence?

This is the code: for (unsigned int i = 0; i < n; ++i) if (i % 2 == 0) ++k; And this is the output for when ...
1
vote
1answer
35 views

How do I create a function from this code? [closed]

Here is the code: for (int i = 1; i < n; i *= 2) ++k; I need to express this as a function. I don't know where to begin.
0
votes
1answer
42 views

Find Recurrence Relation of Code

Suppose A(n) be the number of stars that wrote with the following example. for n>=3, i want calculate the recurrence relation for this code. any idea or solution? ...
1
vote
2answers
71 views

How does this simplification work?

The following recursive function was given: $$T\left(n\right) = T\left(n - 1\right) + x$$ The author stated that by using repeated substitution we can solve the recurrence relation: The basic ...
1
vote
1answer
21 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
1
vote
1answer
39 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
1
vote
1answer
46 views

Problematic Initial Condition of a Recurrence Relation

I encountered this equation, and tried to solve it: $T(n) = T(\sqrt{n})+log(n)$ Under the initial condition T(1)=1. Can someone tell me why is this initial condition helpful? I mean, of course ...
0
votes
2answers
97 views

Meaning of 'expected value' in the following problem

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement: "What is the expected number of dice throws needed to attain a value of at least n (candies, in this ...
2
votes
1answer
31 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
1
vote
2answers
56 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
2
votes
1answer
54 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
0
votes
1answer
23 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
0
votes
1answer
71 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
1
vote
1answer
53 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
3
votes
0answers
39 views

Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [closed]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
1
vote
2answers
49 views

Solve $T(n) = T(n-1)+\log^2(n)$

I was trying to solve $T(n) = T(n-1)+\log^2(n)$ using substitution method and variables substitution but I can't find the correct answer. My attempt: Let $m = \log(n)$ then $T(2^m) = ...
3
votes
5answers
98 views

How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve: $$\begin{aligned} T(1) &= 0 \\ T(2) ...
2
votes
1answer
62 views

Recurrence - using power series

Could you help me in solving this recursion( a closed form ) using power series $\mu(n)=\mu(n−1)k_0+(n−1)\mu(n−2) k_1 \tag 1$, where $k_0,k_1$ are constants $\mu(0)=3,\mu(1)=5$ HINT: We can think ...
0
votes
1answer
25 views

Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
1
vote
1answer
49 views

Infinite series for recurrence

Question 1 If I define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \tag 1$ (where $a_n$ are $3\times 3$ constant matrices indexed with n), then can we re-write $\sum_{n \ge 1} a_{n-1} \frac{z^n}{n!} ...
3
votes
2answers
90 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
0
votes
0answers
24 views

Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
7
votes
3answers
242 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
0
votes
0answers
20 views

Comparing Generalized Continued Fractions

Gosper lays out a method (under Approximations) for comparing regular (a.k.a simple) continued fractions which have all partial numerators set to 1. Continue comparing terms until they differ, then ...
0
votes
0answers
28 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
3
votes
1answer
76 views

Limit of a recursiv trigonometric function

So while doing my math homework I recently stumbled upon this little thing: It seems that $y_n = \sin(y_{n-1}) + k$ with arbitrary $y_0$ and $k$ converges to a definite value for $n \to \infty $. ...
1
vote
2answers
30 views

Finding the inhomogeneous solution

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?
1
vote
2answers
46 views
0
votes
2answers
38 views

Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
1
vote
1answer
25 views

recursive relation for putting signs in 2*n table

Consider we have a $2\times n$ table and we want to put a sign in some of the cells, and we don't put signs in both adjacent cells give a recursive phrase that shows that how many ways we can do that? ...
-2
votes
1answer
43 views

N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
0
votes
1answer
59 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
-1
votes
1answer
46 views

How should I proceed to solve this recurrence relation: $T(n) = T(n - 1)^2$

I tried to solve this recurrence relation, but I was confused when I had to determine the pattern. $$ T(n) = \begin{cases} 3, & \text{if }n = 0 \\ T(n - 1)^2, & \text{if }n > 0 \end{cases} ...
1
vote
0answers
63 views

Solving a Recurrence Relation With Summation and Tau Function

How can I solve the following: $$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$ Where $d(n)$ is the Tau function, and v is the set of values dividing n. e.g. $d(18) = ...
2
votes
0answers
31 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
1
vote
2answers
59 views

Solving this recurrence relation

Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction $$ {\rm ...
0
votes
1answer
73 views

Quadratic Map Solution

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
0
votes
1answer
27 views

Recursive Algorithm Analysis

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ...
1
vote
3answers
174 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
0
votes
3answers
34 views

A closed form for the recursion?

Let $x$ and $y$ be real numbers and $x < y$ Given the recursion: $m_0 = \frac{x+y}{2}$ and $m_1 =\frac{m_0+ y}{2}$, so in general, $$m_i = \frac{m_{i-1} + y}{2}$$.. What is $m_{\infty}$? thanks ...
2
votes
1answer
81 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.
4
votes
3answers
160 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
1
vote
1answer
100 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 ...