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

learn more… | top users | synonyms

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
0answers
47 views

median of three quick sort and recurrence relation [on hold]

How could we prove that median of three quicksort have a running time of \begin{equation*} T(n) = \mathcal{O}(n) + 2T ( n/2) \end{equation*} using induction when it is applied to a sorted array ...
0
votes
2answers
70 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
12 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
43 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
28 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
28 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: ...
-2
votes
0answers
30 views

Writing recurrencies for run time? [duplicate]

Given a function; derp( x, n ) if( n == 0 ) return 1; if( n % 2 == 0 ) return derp( x^2, n/2 ); return x * derp( x^2, (n - 1) / 2); a) I ...
-2
votes
0answers
18 views

Solving recurrencies and recurrence models? [duplicate]

I need help with recurrence in a given code. I solved part (B), I got x^n as what the function is doing, correct me if am wrong. But I have never learned recurrence, help me out with parts C and D. ...
3
votes
0answers
68 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
48 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
22 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
102 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
71 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
43 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
103 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
195 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
766 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
59 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
52 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
80 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
413 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
42 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
97 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
67 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
141 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
47 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
100 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
97 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
67 views
1
vote
2answers
83 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
134 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 ...