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

learn more… | top users | synonyms

2
votes
1answer
29 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
31 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
80 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
66 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 ...
4
votes
1answer
54 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
19 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
49 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
30 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
36 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
79 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
24 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
15 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
33 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
80 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
35 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
740 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
23 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
73 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
31 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
201 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
79 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
56 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
31 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
78 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
50 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
56 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
76 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
71 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
139 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
43 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
79 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
56 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
114 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
73 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
327 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
1k 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
72 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
60 views

Solving complicated recurrence

This question is based on the solution to topcoder SRM-620 question: ...
3
votes
1answer
43 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
55 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
82 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
503 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
47 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) &= ...