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

Proof of big theta using induction

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
18 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
158 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
8 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
76 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
46 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
25 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
72 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
13 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
44 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
30 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 ...
-1
votes
1answer
33 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
71 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
59 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
111 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
40 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
74 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
47 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
108 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
72 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
235 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
834 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
70 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
59 views

Solving complicated recurrence

This question is based on the solution to topcoder SRM-620 question: ...
3
votes
1answer
42 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
53 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
81 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
451 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
43 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
102 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
61 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
73 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
161 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
48 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
64 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
46 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
103 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
48 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
44 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
58 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
152 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 ...