1
vote
1answer
15 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
0
votes
0answers
55 views

Substitution method for solving recurrences

I'm having issues understanding how to solve recurrences via the substitution method. From what I understand, I need to guess the form of the solution first and then use induction to prove that the ...
0
votes
1answer
48 views

The solution of recurrence $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$ is $O(n\lg n)$

Given, $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$. Show that the solution to T(n) is $O(n\lg(n))$. Here's what I tried - Assumption: $T(\lfloor n/2 \rfloor) \le c(\lfloor n/2\rfloor + 17)\cdot ...
0
votes
1answer
41 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? ...
2
votes
1answer
28 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
1
vote
1answer
21 views

Time Complexity of one Challenging Example

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

Which case of the Master theorem applies to the recurrence $T(n)= 100T(n/99)+\log(n!)$?

How to use the Master theorem to solve $T(n)= 100T(n/99)+\log(n!)$? I was given this question, and I can't figure out which case of the master theorem goes here. Thanks for your suggestions.
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 ...
2
votes
2answers
72 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
32 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
28 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
45 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
62 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
23 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
18 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
72 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
292 views

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

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
378 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
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 ...
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
123 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
99 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
56 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
45 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
42 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
48 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
29 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
40 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
134 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
87 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
113 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$. ...
4
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
159 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
259 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
61 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
175 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
40 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
872 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
352 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
193 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
175 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
101 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
707 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 ...