# Tagged Questions

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 ...
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?
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 ...
26 views

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 ...
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. ...
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 ...
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$$ ...