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

learn more… | top users | synonyms

-3
votes
0answers
23 views

Solve Recurrence Equation Problem [duplicate]

I ask this question before, and someone put it as duplicate. i dont know why no one can answer some question, mark question as duplicate. please be kind and let others to know from others. link of my ...
3
votes
0answers
56 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
44 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 ...
-1
votes
0answers
23 views

Can anyone solve this recurrence relation by substitution [duplicate]

Can anyone solve this recurrence relation by substitution T(n)=T(n/2)+nlogn
-3
votes
0answers
19 views

Solve the following recursions using the Akra-Bazzi theorem [duplicate]

Can the following equations be solved using the Akra–Bazzi theorem and how? I don't quite understand the $h_i(x)$ part of the Akra–Bazzi theorem in Wikipedia. I'll appreciate an ...
0
votes
0answers
20 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
86 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
39 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 ...
2
votes
2answers
61 views

Solve recurrence relations

a, Solve this recurrence where $T(0)=0$ and write it in O-notation: $T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$ So, I started to calculate: $T(1)=2(0)+c=c$ $T(2)=1(0+c)+c=2c$ and ...
1
vote
2answers
40 views

Recurrence relations that do not have a closed form solution

A recurrence relation computes value $d_n$ with the $\{d_{i},d_{j}\ldots\}$ previous digits of the sequence So for example, the Fibonacci sequence is defined as follows: $$ F_n = F_{n-1}+F_{n-2},\ \ ...
1
vote
1answer
102 views

Analysis of a recursive algorithm, where running time strongly depends on input

I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $T(x, i, y) = ...
0
votes
0answers
71 views

Recurrence Equation in Algorithm [duplicate]

Can anyone help me in solving this complex recurrence? \begin{eqnarray} T(n) &=& n +\sum_{k-1}^n T(n-k)+T(k) & Where& T(1) = 1. \end{eqnarray} although this topic will already ...
2
votes
2answers
187 views

The Gas Station Problem - fast implementation

Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to ...
8
votes
3answers
716 views

Understanding an algorithm for the gas station problem

In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. ...
2
votes
2answers
68 views

Is there a name for defining recursive functions as an infinite list of input/output pairs?

Recursive functions are usually defined by directly calling a function inside its own body. Nat = Z | S Nat double Z = Z double (S x) = S (S (double x))) What ...
0
votes
0answers
57 views

Solving complicated recurrence

This question is based on the solution to topcoder SRM-620 question: ...
3
votes
1answer
38 views

Solution of complex recurrence relation

Do anyone have any idea how to solve this recurrence?$$T(k) = \sum_{i=1}^{k/2} {k \choose i}T(i)T(k-i)$$ I am working with this kind of recurrence for the first time and don't have much idea of how ...
1
vote
2answers
51 views

Recurrence doesn't add up [duplicate]

I made a recurrence tree and guessed that solution to $T(n)=2T(n-2)+n$ is $O(2^{n/2})$ and I am now trying to prove this through substitution. These are my steps so far, but I can't get it to pass for ...
0
votes
2answers
78 views

solving recurrence by substitution, calculations doesnt add up

I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold $p(n-2) \leq ...
4
votes
2answers
376 views

Solving the recurrence T(n) = 3T(n-2) with iterative method

It's been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given: $$T(n) = 3T(n-2)$$ My first step was to iteratively ...
5
votes
1answer
46 views

Not able to simplify a sum over reciprocals of $\log i$

Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation. Here in this case, I have reached until this point: $$ \begin{align} T(n) &= ...
-1
votes
1answer
39 views

Is my analysis of this recurrence relation correct?

The following recurrence relation, $$T(n)=16T(\frac{n}{4}) + n^2$$ has been given to me to be solved via the Master Theorem. I'm pretty sure this is a case 2 situation, since $$\log_4{16} = 2$$ and ...
2
votes
2answers
92 views

To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

I have done the proof until the point when $T(n) \leq cn^{\log7}$. But when it comes to finding the value of constant $c$, I am getting stuck. The given recurrence relation is $T(n) = 7T(n/2) + ...
2
votes
1answer
40 views

Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$

I met a recurrence equation for my algorithm $$ f(n) = 2\cdot \left( f(n-1) + f(\frac{n}{2}) \right)$$ with $f(1)=1$, $f(2)=4$, $f(3)=10$. I guess it is $\Theta((2+\epsilon)^n)$, where $\epsilon$ ...
0
votes
0answers
16 views

Iteration method - recurrence [duplicate]

How can I find the tightest possible asymptotic bounds on the recurrence T(n) = 3T(n/2)+cn, where c is a positive constant. Must use iteration method.
3
votes
2answers
58 views

Solve the worst case of this recurrence equation

I am trying to find the worst case $Θ$ bound for the following recurrence equation: $$ T(n)=\sum_{i=1}^kT(a_i)+n+\lg k\sum_{i=1}^ka_i\quad where\quad n=1+\sum_{i=0}^ka_i\quad and\quad a_0\ge a_1, a_2, ...
2
votes
1answer
62 views

How to make this recursive relationship nonrecursive? [closed]

I need to make a recursive relationship for a function f(m, n) nonrecursive to make it more efficient and succinct in my code. I stumbled across an important ...
1
vote
1answer
116 views

Recurrence of T(n) = T(n/3) + T(2n/3) [duplicate]

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
-1
votes
2answers
45 views

Solve recurrence [closed]

![enter image description here][1] I have a problem to solve this recurrence. I tried by myself but it doesn't look understandable. Solve the following recurrence
0
votes
3answers
142 views

Solve the recurrence $f(n+1)=f(n)^2,\, f(0)=2$ [closed]

I have a problem with an exercise asking me to solve the following recurrence: $$f(n+1)=f(n)^2, \quad f(0)=2$$ Can someone explain how to solve this? I tried but couldn't.
0
votes
2answers
63 views

How many times can you divide a list of n elements in 1/2 [closed]

I am trying to wrap my head around recursion and divide and conquer algorithms. Can someone provide a proof and explanation of how many times a list of n elements can be divided in 1/2 on both sides.. ...
0
votes
0answers
20 views

Time Complexity Problem [duplicate]

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta ( n)$$ I have been trying to solve this question but I could not find anything. I tried to build recursion tree but I can not find the sum. Do you ...
0
votes
0answers
20 views

Time complexity by solving recurrence relation [duplicate]

I was working on recurrence relation and came across this example T(n) = 2T(n/2) + log(n) What will be the time complexity, ie, big O for this relation. Thanks for any help in advance.
2
votes
1answer
44 views

Recursive Algorithm Analysis

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ...
-1
votes
2answers
91 views

Recurrence Problem $T(n) = 3T(n/3) + n$ [duplicate]

My question here is dealing with the residual that I get. We are trying to prove $T(n) = 3T(n/3) + n$ is $O(n*\log n)$. So where I get is $T(n) \le cn[\log n - \log 3] + n$. So my residual is $-cn\log ...
2
votes
1answer
42 views

Recurrence $T(n) = 2T(\sqrt{n}) + \log n$ [duplicate]

So I have a question for the recurrence $T(n) = 2T(\sqrt{n}) + \log n$. We are to use substitution method to figure out the solution. This is an example problem (not a exercise problem) in my book ...
3
votes
1answer
41 views

Recurrence relation in 2 variables

When analyzing an algorithm, the following recurrence relation popped up: $T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$ where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$. By applying the Master Theorem ...
3
votes
1answer
54 views

How to solve recurrences involving log?

For example, $T(n) = \log {n} \cdot T(\frac{n}{\log{n}}) + \Theta(n)$ I tried using the substitution method with $ n = 2^m $, but that got me nowhere, since it still ends up with a $m$ and $2^m$. ...
0
votes
1answer
64 views

Series where each term is square of previous [closed]

The problem statement is as follows:- In a court case, a judge cited a court of contempt and ordered a fine of $2 for first day. On subsequent days, the fine would be equal to the square of the ...
1
vote
1answer
66 views
1
vote
2answers
82 views

Why can any polynomial and exponential be represented as a recurrence?

I posted this question on math.SE but I haven't got any reply so I'm posting here also. I am reading The Algorithm Design Manual by Steven S Skiena. In Section 4.10.1 Recurrence Relations, I ...
3
votes
1answer
31 views

Pick parameter function that minimises whole function

I have a recursive algorithm defined by the following recursion. $$T(n) = T(n/f(n)) + O(\log f(n)).$$ I want to find the function $f$ that minimizes $T(n)$. If $f$ is a constant then $T(n) = ...
2
votes
2answers
125 views

How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
2
votes
2answers
122 views

Solution to recurrence $T(n) = T(n/2) + n^2$

I am getting confused with the solution to this recurrence - $T(n) = T(n/2) + n^2$ Recursion tree - ...
0
votes
1answer
83 views

Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$

Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$? The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c > ...
3
votes
3answers
84 views

How do I show T(n) = 2T(n-1) + k is O(2^n)?

This is a practice problem I've come up with in order to study for an exam I have in a couple of hours. Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant. ...
2
votes
1answer
228 views

Finding growth of “inter-recursive” functions

consider following code int f(int x) { if(x<1) return 1; else return f(x-1)+g(x); } int g(int x) { if(x<2) return 1; else return f(x-1)+g(x/2); } ...
-1
votes
2answers
83 views

Recurrence for total number of extraneous key insertions in a hash table

I have a practice exam question that I don't know how to set up a recurrence for. It is dealing with a hash table. The question is as follows: Suppose that a hashing strategy is designed so that ...
4
votes
0answers
55 views

Are there master theorems that deal with parameters of the form $n-c$?

While thinking about this question on a recurrence I checked out some stronger master theorems. Unfortunately, they do not seem to apply because terms $\qquad\displaystyle T(n) = \dots + T(n-1) + ...