All Questions
12 questions
1
vote
1
answer
103
views
Data Structure - Minimum time to copy a file into all Nodes
I have a below problem statement and it seems like it can be solved using dynamic programming (recurrence relation) but not able to solve it.
Problem statement: - There are N identical nodes(identical ...
- 362
0
votes
1
answer
1k
views
Recurrence Relation to find Big Theta
T(n) = 7T(n/2)+3n^2+2. I cant quite figure out how to solve this recurrence relation to get the Big Theta Notation. I have just started DSA so please help me out here.
1
vote
2
answers
241
views
Is there any solution for recurrence relation T(n) = T(T(n - 1)) + 1?
Is there any solution for this Recurrence relation
T(n) = T( T( n - 1 ) ) + 1
from code in C like syntax
Algo(int n)
{
printf("%d ->",n);
return (n >= 1)?Algo(Algo(n - 1))+1:1;
...
- 13
-2
votes
1
answer
100
views
What is the pseudocode for this recurrence relation
2T(n-1) - 1 if n >1
1. Else
What would be the pseudocode for this recurrence relation?
I am not able to find out the program in which this recurrence relation would be applied . As this ...
3
votes
2
answers
592
views
Buy Sell Stock with Transaction Fee?
I am trying to solve the problem and come up with a recurrence relation that answers it correctly. Code :
private static int recurse( int[] prices, int index, int[][] dp ) {
if (index == prices....
- 427
0
votes
1
answer
121
views
What is the runtime and recurrence relation of the check BST function?
How do I get the base case and the overall runtime of this code snippet:
maxN -> gets the maximum value at the subtree = O(log n)
minN -> gets the minimum value at the subtree = O(log n)
...
- 11
-1
votes
1
answer
418
views
Solve using either master theorem or by expansion
I have two questions, which I have trying but unable to figure them out.
1) 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑛^4
2) 𝑇(𝑛) = 2𝑇 (𝑛/2) + 𝑛 lg 𝑛
For first one, I am assuming substitution (am I correct?), and ...
-2
votes
1
answer
169
views
Solve Recurrence Relation by Master theorem? [closed]
Can someone please clarify this solution a little more?
T(n) = 2T(n^1/2) + log n
Solution:
Let k = log n,
T(n) = T(2^k)=2T(2^(k/2)) + k
Substituting into this the equation S(k) = T(2^k)
we get ...
- 709
0
votes
1
answer
96
views
Recurrence Equation for algorithm
I'm pretty new to recurrence equation concepts, need help with following algorithm
G(n)
Require: A positive integer n.
if n <= 1 then
return n
else
return 5*g(n - 1) - 6* g(n- 2)
end if
I came up ...
- 757
0
votes
1
answer
494
views
Expanding Recurrence Relation and Finding Closed Form
I have a snippet of algorithm and must find the worst-case recurrence and find its closed form. So far I have the worst-case recurrence:
T(n)= 2T(n/4) + C for n > 1.
I tried expanding it, and I ...
- 85
2
votes
1
answer
2k
views
recurrence relation on a Merge Sort algorithm
The question is :
UNBALANCED MERGE SORT
is a sorting algorithm, which is a modified version of
the standard MERGE SORT
algorithm. The only difference is that instead of dividing
the input into 2 ...
- 681
2
votes
2
answers
6k
views
Solution for recurrence T(n)=t(n/2)+sqrt(n) using induction only [closed]
I am looking to prove that T(n)=T(n/2)+sqrt(n) is O(sqrt(n)) given T(1)=1
using only induction.
It is easy to solve using the Master theorem but this is not the case.
I tried to assume
T(n/2) < ...
- 141