Linked Questions
251 questions linked to/from Solving or approximating recurrence relations for sequences of numbers
5
votes
2answers
18k views
$T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]
According to Introduction to algorithms by Cormen et al,
$$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why?
And which case of master theorem is it?
1
vote
2answers
6k views
What is the complexity of recurrence $T(n) = T(n-1) + 1/n$ [duplicate]
What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$
I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be $T(n-...
-1
votes
1answer
8k views
Solving $T(n)= 3T(n/4)+ n\log n$ without the master method [duplicate]
How can one solve
$$T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log n$$
without using the master method?
I know it has a solution using the master theorem from this link.
1
vote
1answer
5k views
Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$ [duplicate]
Possible Duplicate:
Solving or approximating recurrence relations for sequences of numbers
I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $ T(n) = O(n \log(n))$
But how do you get to ...
0
votes
4answers
3k views
Applying Master Theorem to: T(n) = T(n - 2) + n^2 [duplicate]
I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation:
T(n) = T(n-2) ...
4
votes
2answers
2k views
Algorithms - Solving recurrence-relations/Bounds? [duplicate]
I'm currently in a course, and I for the life of me cannot figure out what my professor is doing. I could really use a working example, and I was hoping someone here might oblige.
Suppose we have ...
1
vote
1answer
5k views
Recurrence relation T(n) = 3T(n-1) + n [duplicate]
I'm trying to solve the recurrence relation T(n) = 3T(n-1) + n and I think the answer is O(n^3) because each new node spawns three child nodes in the recurrence tree. Is this correct? And, in terms of ...
3
votes
1answer
4k views
Recurrence relation with sum [duplicate]
This is a question about recurrence relation that contains sum inside the recursion.I am totally stuck. Can anyone help?
The problem asks to solve the following recursion $T(n)=\frac{1}{n} \sum_{i=1}^...
2
votes
3answers
1k views
Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1 [duplicate]
Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and $T(1)=1$.
My attempt: I tried back substituting but I am unable to find a general pattern:
$$\begin{align*}
T(n) &=2^2 T(n-2)...
-1
votes
2answers
2k 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 ...
0
votes
2answers
2k 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
=T(((3n-3a)+n)-...
-1
votes
1answer
1k views
How can I solve for T(n) recurrence equations? [duplicate]
Solve the following recurrence equations
a. T(n) = T(n/2) + 18
b. T(n) = 2T(n/2) + 5n
c. T(n) = 3T(n/2) + 5n
d. T(n) = T(n/2) + 5n
This is only a sample of what I was given but I am not sure what ...
1
vote
1answer
1k 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:
...
1
vote
2answers
591 views
How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$? [duplicate]
How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$?
We assume that $T(n)$ is constant for sufficiently small $n$.
0
votes
1answer
2k views
How do you solve a recurrence relation with multiple subproblems of different sizes? [duplicate]
For instance, consider the following recurrence relation.
T(n) = T(n/2) + T(n/3) + T(n/4) + n
Would you use the substitution method for this?