All Questions
Tagged with recurrence data-structures
22 questions
0
votes
0
answers
47
views
What would be the time complexity of finding Power set of an array?
The task is to find the Power Set of an array which is to find set of all subsets of an array for example for [1,2] it will be [[],[1],[2],[1,2]]. For an n length array, the power set is 2^n long. It ...
- 145
0
votes
1
answer
593
views
Recurrence relation: T(n) = n*T(n/2) [closed]
I've been trying to solve this problem but I am stuck at the last bit and my University lecturer doesn't really want to help me :)
T(1) = 1
T(n) = n*T(n/2)
T(n/2) = n/2 * T(n/4);
T(n/4) = n/4 * T(n/8);...
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
-1
votes
1
answer
246
views
Recurrence: T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n) , what is the complexity of T(n)?
how to solve the recurrence equation . T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n).
I can solve it if instead of Ω(n), we had (n), but now I can't solve it. please help me!
2
votes
1
answer
44
views
Using recurrence tree, solve the recurrence T(n) = T(n − 1) + O(n) [closed]
Please Explain it.Using recurrence tree, solve the recurrence T(n) = T(n − 1) + O(n)
-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
51
views
Data Structure, Recursive functions
I have tried several times to find the answer of this question and every time my result is 30 but the answer key shows the result to 32 and I don't understand why it should be 32??!! it is a data ...
- 3
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 ...
3
votes
1
answer
75
views
what is wrong with my recursion code?
I have a recurrence series so i have converted into recursion form.
But it will show as maximum stack size reached.
The same code is working with n=4 as fn(4) and working correctly but not working ...
- 453
-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