0
votes
1answer
14 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 ...
3
votes
2answers
70 views

The growth of the solution of the recursive relation $P(n)=\sum_{k=1}^{n-1} P(k) P(n-k)$

According to my notes,one solution of the recursive relation: $$P(n)=\sum_{k=1}^{n-1} P(k) P(n-k), \text{ for } n>1 \\ P(1)=1$$ is $\Omega(2^n) $. How do we conclude that this is one solution?
1
vote
0answers
29 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
0
votes
1answer
26 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
2answers
44 views

Complexity of $T(n) = 2T(n/2) + n$

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$? How can I continue from here? $T(n) = 2T(n/2) + n,$$T(n) = 4T(n/4) + ...
0
votes
0answers
61 views

Recurrence equation analysis of the form T(x) = t + max{T(…) + …}

I want to find the worst-case running time of an algorithm I came up with, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $$ ...
0
votes
1answer
67 views

Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
0
votes
0answers
20 views

What is the asymptotic bound of the recurrence : $T(n)= 2T\frac{n}{2}+\log n$?

I have managed to reach upto : $T(n) = 2.n.\log n - \log n - [2+2.2^2 +3.2^3 + \dots\log_2 n.2^{\log_2 n}]$ I m stuck here and not getting any clue how for solving the arithmetico-geometric series. ...
0
votes
0answers
16 views

Can someone help me solve this recurrence using the Master Theorem?

Can someone help me solve this recurrence? $$T(n)= T(n^{1/2}) + Θ(\log\log n)$$ I know that I have to change the variables $m=\log n$. Then I have: $$S(m)=S(m/2)+Θ(\log m)$$ Case 2 of Master ...
1
vote
1answer
16 views

third order recurrence relation with non-constant coefficients

Does anyone know of a paper that may have been written on $3^{rd}$ order recurrence relations with polynomial coefficients, that is, one of the form $$A(n)a_{n+3}+B(n)a_{n+2}+C(n)a_{n+1}=D(n)a_n$$ ...
3
votes
1answer
70 views

Solving a recurrence for a random walk revisited

I previously asked about the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < ...
2
votes
1answer
35 views

Recurrence relation and big-O-notation

Consider the following recurrence relation: $$T(n)=c\cdot + 2\cdot T(n/2)$$ This is the recurrence relation for the Merge-Sort algorithm. How can one deduce from this equation the time complexity of ...
1
vote
1answer
183 views

Solving the recurrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$

I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$ Here's my attempt: If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ ...
0
votes
3answers
262 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
95 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
25 views

Analyzing $n_{i+1} = n_i - n_i^{3/4}$

I have a non-linear recurrence given by $$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$ Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation? I'm ...
4
votes
1answer
122 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...
1
vote
2answers
97 views

What is the order of growth of the parameterized recurrence relation given below?

Given two parameters $a$ and $b$ (both positive integers), please estimate the order of growth of the following function: $$F(t)=\left\{\begin{array}{ll} 1, \, &t\le a \\ F(t-1) + b\cdot ...
3
votes
1answer
55 views

Equivalent of a recurrence sequence [duplicate]

Let $x_{0} = 2$ and $x_{n+1} = x_{n} + \ln(x_{n})$, how can I find an asymptotic equivalent of this sequence say, to the third term? (This is not homework, it was a problem in the Oral Examination ...
0
votes
2answers
41 views

Algorithm Analysis on Recurrence Relation.

Consider the following recurrenc relation: $f(n) = f(n/2) +nlogn$ Since this does not honor the form of the Master Recurrence, we need to obtain an estimate of the asymptotic order of $f$. According ...
0
votes
1answer
41 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...
0
votes
2answers
36 views

Show Time $T(n) = Θ(n^3)$

I have to show that : $$T(n) = Θ({n^3})$$ We have this recursive function : $$T(n) = 8T(n/2) + n^2, n>=2$$ also we know that $$T(1) = 1$$ And it says that there is a "replacement method" to ...
1
vote
1answer
46 views

How to prove that sum given by generating function diverges for given value of $x$

I have a generating function: $A(x)=\dfrac{3-8x}{1-4x+6x^2-3x^3}$ (also I have a recurrence from which this function is built). I have to prove that sum $\sum\limits_k a_k\left(\dfrac{4}{3}\right)^k$ ...
0
votes
1answer
28 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
1
vote
1answer
39 views

getting T(n) when I get bigTheta complexity from recurrence relation

I wonder how could I solve the recurrence relation when I calculate complexities. Let me explain it via an example: $T(n)=2T(n/2) +n$. Solve this recurrence relation. I know from the Master theorem ...
1
vote
2answers
123 views

Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$

Please help me solve the recurrence $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n) $$
0
votes
0answers
29 views

Asymptotics for a recurrence relation

Here we have $T(1)=1$ and $$T(n)=T(n-1)+T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n.$$ How to show its asymptotics? I suppose it's $n^{\Theta(\log n)}$, but not sure. For the question here, ...
0
votes
3answers
85 views

Recurrence Master Theorem Question

Solve the recurrence $$T(n) = T({2n\over5}) +n$$ My attempt: $a=1$,$\ b=\frac 52$, $f(n)=n$ For the most part I believe that is correct. Now I was wondering if my math is correct in this next ...
1
vote
2answers
175 views

Bounds for $T(n) = 2T(n/2) + n/\lg{n}$

I've been trying to find tight bounds for the equation: $$ T(n) = 2T(n/2) + n/\lg{n} $$ The master method does not apply since $n/\lg{n}$ is not polynomially smaller than $n$. So far I've found that ...
10
votes
1answer
111 views

Find asymptotic of recurrence sequence

Given a sequence $x_1=\frac{1}{2}$, $x_{n+1}=x_n-x_n^2$. It's easy to see that it limits to $0$. The question is: is there exists an $\alpha$ such, that $\lim\limits_{n\to\infty}n^\alpha x_n\neq0$. ...
3
votes
1answer
2k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
5
votes
1answer
158 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
9
votes
1answer
255 views

What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?

Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
0
votes
1answer
60 views

Solve the recurrence $T(n) = T(\log_2 n) + 13n$

I have the following recurrence relation $$T(n) = T(\log_2 n) + 13n.$$ I believe in order to solve the equation I need to determine the height of the tree. $$T(n) \to T(\log_2 n) \to ...
1
vote
1answer
173 views

An issue with approximations of a recurrence sequence

By trying to give an approximation to a given recurrence sequence I encountered a problem. To be more precise I have a method but it fails if the right condition is not met and I wonder how I should ...
0
votes
1answer
39 views

Master Method and use cases

$T(n)=T(n-2)+n^{2}$ and $T(n)=4T(n-2)+n^{2}$ Master method to solve these two equations? I know I can use the other cases where $a$ and $b > 0$ but since $T(n-2)$ do I assume $b$ is $1$?
1
vote
1answer
804 views

Solving a recurrence realtion using backward substitution.

So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P I start off with this ...
0
votes
1answer
339 views

Solving Recurrence Relation with Forward Substitution

I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with $$ T(n) = 4T(n/3) $$ For all $n > 1$ ...
3
votes
4answers
188 views

Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$

Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$: $$ T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n) $$ ...
1
vote
2answers
170 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
1
vote
2answers
100 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
0
votes
1answer
684 views

solving recurrence relation by substitution method and find asymptotic bound

Solve the following recurrence relations and give a bound for each of them. $T(n)= 2T(n-3)+1$ $T(n) = 5T(n-4)+n$
1
vote
1answer
85 views

Asymptotic behaviour of $f(x) =f(\sqrt{x}) + \sqrt{x}$

I stumbled about this recursive function today: $$f_n = f_\sqrt{n} + \sqrt n$$ I tried to solve it with substitution ($m = \log_2 n, \quad g_{2^m} = g_{2^{m/2}} + 2^{m/2}$), but I have a bad feeling ...
0
votes
2answers
75 views

Wby can't this recurrence be solved by direct guessing?

I'm reading Introduction to Algorithms by Cormen et. al. and in a part there, they say that this recurrence : T(n)=T(n/2) + T(n/2) + 1 can't be proved by the ...
0
votes
2answers
152 views

Resolve this recurrence: $T(2^n) = T(2^{n-1}) + 2^n$

I need to resolve this recurrence: $$T(2^n) = T(2^{n-1}) + 2^n$$ The conditions are: Give a $\theta$ bound. In case that cannot find a $\theta$ bound, provide tight upper ($O$ or $o$) and lower ...
0
votes
1answer
102 views

Showing a recurrence is $\Theta$(n)

Specifically how do you go about showing that $$ 2T(n/2)+1 =\Theta(n) $$ Not looking for an answer, as much as the process? I'm studying for a test and this is one of the review problems. Thanks in ...
0
votes
1answer
181 views

How do you get the upper bound over this recurrence?

$$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n^2}{\log n}$$ I have the solution here (see example 4 in that pdf), but the problem is that they have solved it by guessing. I couldn't make that guess. ...
0
votes
2answers
60 views

Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n) = \Theta(n^2) $ for the recursion $T(n)= 4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2 $. I don't understand how to subtract off ...
1
vote
1answer
51 views

Estimation of recurrent sequence

Suppose we have $z_{n+1}=\frac{z_{n}^2}{1+cz_{n}}$ where $c>1$ and $z_{1}>0$. What can we say about $z_{n}$? Can we find an explicit formula? Can we at least get an approximation of the form ...
2
votes
2answers
84 views

Asymptotics of $nT(1) + \frac{n}{\lg5}\sum_{i=1}^{\log_5 n}\frac{1}{i}$

I am trying to find asymptotics/running time of recurrence $T(n) = 5T(\frac{n}{5}) + \frac{n}{\lg n}$. Since Master Theorem for solving the reassurances can't be used, I was able to unroll it and came ...