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

learn more… | top users | synonyms

1
vote
1answer
32 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
51 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
31 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
35 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
7 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
128 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
32 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
47 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
28 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
52 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
58 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
61 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
43 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
168 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
74 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
56 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
33 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
48 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
89 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
42 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
81 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
745 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
86 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
51 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
231 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
81 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
36 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
87 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
32 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
78 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: ...
3
votes
0answers
79 views

Solve Recurrence Equation Problem [duplicate]

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 to substitute $n=3^m$, ...
-3
votes
1answer
80 views

Satisfying all the conditions of case 3 of the Master Method except the regularity condition

The regularity condition of case 3 of Master Method says that $af(n/b) < cf(n)$, for $c < 1$. How to devise a recurrence relation that satisfies all other conditions of case 3 except the ...
0
votes
0answers
23 views

How to guess solutions for “divide and conquer” type of recurrences? [duplicate]

I am trying to solve "divide and conquer" recurrence relations of the type $T(n) = a T(n/b) + f(n)$ using the Substitution/Inductive Methods ( NOT the Master Theorem ). Every site I see on the web ...
3
votes
1answer
161 views

Master Method to solve recurrences is 'a' related to 'b'?

The master method allows us to solve certain recurrences of the form $$T(n) = aT(n/b)+f(n)\,,$$ where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further ...
1
vote
0answers
44 views

Dynamic Programming - Seemingly unnecessary recursion?

I am working on my thesis on revenue management. I have been over the following problem multiple times now, but I fail to see where my mistake is. This example is based on The Theory and Practice of ...