a definition of a sequence where later elements are expressed as a function of earlier elements.

learn more… | top users | synonyms

0
votes
0answers
7 views

Generating Function and Recurrence Relation in Contest? [migrated]

What is the generating function for the sequence $\{a_n\}_{n \geq 0}$, defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ for $n \geq 1$. ...
-1
votes
0answers
15 views

The substitution method for solving recurrences [duplicate]

I'm having a lot of trouble using the substitution method to solve the exercises in CLRS section 4.3. The explanation seems inadequate to solve the problems, there's no answers in the solution manual ...
0
votes
1answer
12 views

Solution to the following recurrence relation and initial condition? [duplicate]

With the initial condition being $a_0$ = 3, and the relation being $a_n = 2a_{n - 1}$, what would the solution be? Any help would be greatly appreciated.
0
votes
1answer
27 views

How to solve this recurrence using recursion tree method

How to solve this using the recursive tree method? I'm stuck with the $\max$. $$T(n) = T\left(\left\lceil \frac{n}{\max\,\{\sqrt{n},2\}}\right\rceil\right) + n\,.$$
0
votes
0answers
34 views

why this recurrence can be solved by Master method? [duplicate]

I have studied the following recurrence. The ratio between f(n) and n^log_b(a) is log n so there is non polynomial difference but I have studied from book that it can be solved by master method. $T ...
0
votes
1answer
24 views

Problem with Understanding a Recursion Tree

Consider the recursion tree: $T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$. I determined that there are at most $1 + log_{4}\ p$ levels, because the longest simple path from root to leaf is $p ...
1
vote
1answer
48 views

How to write recurrence relation for the following scenario?

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function $g(x)$ for each node x. If the cost of computing $g(x)$ is min{no. of leaf-nodes in ...
0
votes
2answers
56 views

Solution verification: solving $T(n) = T(n-1) + 2/n$

I was wondering if someone could possibly verify my solution to the following: I'm trying to solve the recurrence relation $T(n) = T(n-1) + 2/n$. To get it into the form of the Master Theorem, I note ...
0
votes
0answers
30 views

Solving $T(n) = 7T(n/2) + n^2 + \log(n)$ [duplicate]

I'm working on a problem set for my algorithms course and we're asked to solve the recurrence relation $$ T(n) = 7T(n/2) + n^2 + \log(n). $$ Since this recurrence relation is not of the form $T(n) = ...
-1
votes
1answer
35 views

Solving Recurrence Relations 3 [closed]

Consider the following recurrence $$T(n)=T(n-1)+n\log n$$ My approach: Solving using Substitution $T(n)=n \log n+(n-1) \log (n-1)+(n-2) \log (n-2)+(n-3) \log (n-3)+...$ $=[n\log n + n \log(n-1)+ n ...
0
votes
0answers
18 views

Approximating Recurrence Relations [duplicate]

Consider the following recurrence relation $$T(n)=2\times T(n-1)+n$$ $$T(1)=1$$ My approach: On Solving using Substitution I ended up here $2^{n-1}T(1)+2^{n-2}T(2)+...+2^2(n-2)+2(n-1)+n$ How to ...
1
vote
1answer
37 views

Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$ [duplicate]

Let the sequence $r$ be defined by: $$\begin{align*}r_{1} &= 1\\ r_n&= 1 + r_{\lfloor\sqrt{n}\rfloor}\,,\quad n\geq 2\,.\end{align*}$$ Prove by induction that $r_n$ is $O(\log_2(\log_2n))$. ...
1
vote
1answer
8 views

Finding a solution to the following conditions? [duplicate]

So for these 5 conditions, I am trying to find the solution/formula for them. What would $a_n$ equal basically? If it helps, the recurrence relation these 5 conditions were generated from was $a_n = ...
9
votes
2answers
139 views

Efficient algorithm to compute the $n$th Fibonacci number

The $n$th Fibonacci number can be computed in linear time using the following recurrence: ...
0
votes
1answer
34 views

Merge Sort proof [duplicate]

I am trying to prove that merge sort is indeed $O(n \log n)$. I was able to extract a pattern using constants, however now I am stuck. This is as far as I can get: $T(n) = 2T(n/2) + cn$ $T(n/2) = ...
5
votes
1answer
49 views

Why is $\sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]=2^n$?

In CLRS book, in the road cutting example there is a recursion formula $$ 1+\sum_{j=0}^{n-1}T(j) $$ and it can be proved that the sum is $$ 2^n $$ by simple induction. In 3-rd ...
2
votes
1answer
30 views

Solving recurrence relation

I am trying to find a $\Theta$ bound for the following recurrence equation: $$ T(n,p,k)=T(n,p,k/2)+T(n,p/4,k)+T(n/8,p,k)+npk $$ ...
0
votes
1answer
54 views

Solving a recurrence relation using Divide and Conquer Master Theorem [duplicate]

For the recurrence relation $$T(n) = 16T(n/4) + n!\,,$$ I have found that $T(n)\in Θ(n!)$. Can this be deduced using the Master Theorem?
2
votes
1answer
59 views

Closed-form solution to recurrence equation

I have a recurrence relation of the form: $f(0) = f(1) = 1, f(2) = 2$ (initial conditions). $f(2n) = f(n+1) + f(n) + n$ for $n>1$. $f(2n+1) = f(n) + f(n-1) + 1$ for $n>1$. I have been able ...
3
votes
2answers
64 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...
1
vote
1answer
45 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
1
vote
1answer
86 views

What kind of recurrence relations has p < 0?

By the master method, $T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$ where $p$ is real. I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p<0$?
3
votes
1answer
201 views

How many comparisons do we need to find min and max of n numbers?

Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers. Recurrence for the above problem ...
6
votes
1answer
75 views

Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$

I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input. The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$. It ...
0
votes
0answers
22 views

What kinds of recurrence relations can be involved in a tabulation solution?

We all know F(n) = F(n-1) + F(n-2) is an easy example. We can compute this by using DP. But what about F(n) = F(n-1) + k, we could compute this by tabulation but would you still call it DP? Also, ...
3
votes
1answer
59 views

Making a conjecture of a closed form

There's a formula given $$ T(m,n) = \left\{ \begin{array}{l l} 1 & \quad \text{if $m=0$}\\ 1+T(n \mod m, m) & \quad \text{if $m>0$} \end{array} \right.$$ We're told to use ...
1
vote
0answers
33 views

Is there a closed-form formula for this recursive sequence? [duplicate]

Let $k > 0$ be an integer. Define $A_n$ as follows: $$ A_n = \begin{cases} n & \text{if } n < k, \\ \sum_{i=0}^{k-1} i & \text{if } n = k \\ \sum_{i=1}^k A_{n-i} & \text{if } n ...
0
votes
1answer
36 views

Solve a recurrence relation with two recursion calls using the iteration method [duplicate]

I can't figure out how to solve this recurrence relation using the iteration method: $$T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if $n=1$} \\ 3T(n-1)+ 4T(n-2), & \text{if ...
0
votes
2answers
52 views

recurrence - Iteration method T(n)=T(n-a)+n [duplicate]

I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1. So I started to iterate T(n)=T(n-a)+n =T(((n-a)+n)-a)+n =T(3n-3a)+n ...
2
votes
1answer
90 views

Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary ...
0
votes
1answer
25 views

Prove the upper bound on $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$ [duplicate]

I need some help with the following recursion: $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$ More specifically I wish to find and prove the upper bound on it. I have a hunch it ...
1
vote
0answers
16 views

How to solve the following recurrence: g(n) = g(log n) + n^(1/2) [duplicate]

Doesn't fit the Master method, and I am not sure where to go from here. Thanks
3
votes
1answer
43 views

Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log_b a}$: $$ T(n) = 2T\left(\frac{n}{2}\right) + ...
0
votes
1answer
82 views

Recurrence relation with a number value (not n) [duplicate]

I'm learning how to use recursion trees to solve recurrence relations and while I know how to solve it for the form $$T(n) = aT\big(\frac{n}{4}\big) + n$$ I'm stuck when the equation has a numerical ...
0
votes
0answers
36 views

Setting up a recursion tree

My textbook shows that when setting up a recursion tree for a recurrence, like $$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$ you place the cn^2 term at the root to represent the cost of at the top level ...
6
votes
1answer
750 views

What is the Big O of T(n)?

I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,. $$ I've established that $T(n) = \frac{1}{n}$ but now ...
0
votes
0answers
24 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
1
vote
1answer
90 views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
1
vote
1answer
52 views

Can there exist a recurrence relation for “sequential search”?

I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.
8
votes
1answer
249 views

Solving recurrence relation with two recursive calls

I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very. In order to do this I ask myself the question ...
1
vote
0answers
9 views

Trying to understand the iterative method for solving recurrences in this example [duplicate]

This question: Solving the recurrence T(n) = 3T(n-2) with iterative method has a pretty straightforward step-by-step for solving this particular recurrence. But, I'm having trouble understanding two ...
1
vote
2answers
82 views

Finding recursion for runtime of code [duplicate]

This is the first time we have to do recursive/closed form expressions WITH code in class and I really have no idea how to approach this. My course notes that the prof put up don't really help as he ...
0
votes
0answers
29 views
1
vote
1answer
68 views

Intuition behind recurrences with growth O(n log n) vs O(n²)

Been trying to get the intuition behind why two very similar recurrence relations don't follow a pattern I would expect. They are pretty well known relations: Relation 1 - $T(n) = 2T(\frac{n}{2}) + ...
0
votes
0answers
37 views

Not sure if my recurrence is correct for T(n) = 2T(n^.5) + O(1) [duplicate]

I have T(n) = 2T(n^.5) + O(1) = 2(2T(n^.25) + O(1)) + O(1) = 2(2(2T(n^.125) + O(1)) + O(1)) + O(1) and so on To me this seems wrong, and I ...
0
votes
2answers
88 views

How to simplify the sum over 1/i?

With the recurrence relation: $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$ The "sum for all levels" in the recurrence tree is: $$ \sum_{i=0}^{\log n -1} \frac{n}{\log n - i} = ...
0
votes
0answers
14 views

Solving Recurrence Relations [duplicate]

T(n) = 3T(n/3) + n/ lg n How do you solve this recurrence relation. I know that f(n) = n lgn, a = 4, b = 3. I know that n^(log34) = n^1.261. Then what is the case . I believe that both equations ...
1
vote
1answer
51 views

time complexity [duplicate]

$$ T(n)=\sqrt{n}T(\sqrt{n})+n $$ $$T(1)=T(2)=1$$ the answer is given as $$ \Theta(n\log \log n) $$ I tried to draw recursion tree, it got all crazy I tried using substitution method instead ...
1
vote
1answer
34 views

How do I solve interdependent recurrence relations?

I have three functions with values given as $$\begin{align*} P(0) &= 0 \quad & P(i+1) &= 5M(i)\\ M(0) &= 1 \quad & M(i+1) &= R(i) + 2P(i)\\ R(0) &= 3 ...
0
votes
1answer
92 views

Proving number of calls made in cut-rod algorithm [duplicate]

I was reading dynamic programming chapter from famous book Introduction To Algorithm In rod cutting problem it gives simple algorithm as follows: ...