Register

Recent questions tagged recurrence-relation

1 votes
1 answer
632
Recurrence
How to build Recurrence relation for Time complexity double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } }
How to build Recurrence relation for Time complexity double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += f...
User Avatar
3 votes
1 answer
633
How to solve this recurrence relation?
Solve the equation: $a_n = 5a_{n/3} + 7, \;\; a_1 = 5$ Note: $a_0$ is not given.
Solve the equation: $$a_n = 5a_{n/3} + 7, \;\; a_1 = 5$$Note: $a_0$ is not given.
User Avatar
1 votes
1 answer
634
Recurrence relation
Recurrence relation T(1)=1 T(n)=2T(n-1)+n n>=2 evaluates to .. Pls explain with detailed steps..
Recurrence relation T(1)=1 T(n)=2T(n-1)+n n>=2 evaluates to ..Pls explain with detailed steps..
User Avatar
1 votes
1 answer
635
Recurrence relation
How to solve the Recurrence relation T(n)=T(n/4)+T(3n/4)+n
How to solve the Recurrence relation T(n)=T(n/4)+T(3n/4)+n
User Avatar
1 votes
1 answer
636
order of the algorithm
T(n) = T(n-1)+ 1/n if n>1 =1 otherwise The order of the algorithm is
T(n) = T(n-1)+ 1/n if n>1 =1 otherwiseThe order of the algorithm is
User Avatar
1 votes
2 answers
637
Recurrence Relation
T(n) = T(n-1) + T(n-2) + c i want solve it using substitution method.. T(n) <= 2 T(n-1) + c is this a correct way ?? plz explain ... if its wrong then what is correct way
T(n) = T(n-1) + T(n-2) + c i want solve it using substitution method..T(n) <= 2 T(n-1) + c is this a correct way ??plz explain ...if its wrong then what is correct w...
User Avatar
2 votes
0 answers
639
Find the recurrence
User Avatar
2 votes
1 answer
642
Can these be solved by Master's theorem?
1) $T(n)=T(n/2)+2^n$ 2) $T(n)=2T(n/2)+n / \log n$ 3) $T(n)=16T(n/4)+n!$ 4) $T(n)= \sqrt 2T ( n/2 ) + \log n$
1) $T(n)=T(n/2)+2^n$2) $T(n)=2T(n/2)+n / \log n$3) $T(n)=16T(n/4)+n!$4) $T(n)= \sqrt 2T ( n/2 ) + \log n$
User Avatar
7 votes
3 answers
643
T.C of T(n)=2T(n-1)+n,n >1 ,T(1)=1 ?
T.C of T(n)=2T(n-1)+n,n > 1 ,T(1)=1 ?
T.C of T(n)=2T(n-1)+n,n 1 ,T(1)=1 ?
User Avatar
3 votes
3 answers
646
How can one solve the following recurrence?
$T(n)\quad=\quad T(n-1)+T \left (\frac{n}{2} \right )+n$ $n \geq 1, \quad T(1)=1$
$$T(n)\quad=\quad T(n-1)+T \left (\frac{n}{2} \right )+n$$ $$n \geq 1, \quad T(1)=1$$
User Avatar
1 votes
3 answers
647
What is the time complexity of the given recurrence relation ?
Consider the given recurrence relation , find the time complexity ? T(n)=2T(n-1)+T(n-2)+C, T(0)=T(1)=1  
Consider the given recurrence relation , find the time complexity ?T(n)=2T(n-1)+T(n-2)+C, T(0)=T(1)=1 
User Avatar
0 votes
3 answers
648
time complexity
Find time complexity int R(int n) { if(n<=1) return 1; else { int sum=0; for(int i=1;i<=n;i=i*2) for(j=1;j<=i;j=j*2){ sum=sum+i; sum=sum*R(n/2); } } return sum; }
Find time complexity int R(int n) { if(n<=1) return 1; else { int sum=0; for(int i=1;i<=n;i=i*2) for(j=1;j<=i;j=j*2){ sum=sum+i; sum=sum*R(n/2); } } return sum; }
User Avatar
2 votes
3 answers
652
Can masters theorem solve the recurrence 4T(n/2) + (n^2).logn ?
Can masters theorem solve the recurrence 4T(n/2) + n2.logn ?  it is said that it falls between the case 2 & 3 and no solution possible with this method .can anyone explain it clearly ?  
Can masters theorem solve the recurrence 4T(n/2) + n2.logn ? it is said that it falls between the case 2 & 3 and no solution possible with this method .can anyone explai...
User Avatar
2 votes
2 answers
653
What does fun2() do in general in the below recursive code ?
int fun(int x, int y) { if (y == 0) return 0; return (x + fun(x, y-1)); } int fun2(int a, int b) { if (b == 0) return 1; return fun(a, fun2(a, b-1)); }
int fun(int x, int y) { if (y == 0) return 0; return (x + fun(x, y-1)); } int fun2(int a, int b) { if (b == 0) return 1; return fun(a, fun2(a, b-1)); }
User Avatar
1 votes
1 answer
654
Solve the recurrence
T(n) = T(n - 1) + 1/n a) O(1) b) O(n) c) O(log n) d) O(log log n)
T(n) = T(n - 1) + 1/na) O(1)b) O(n)c) O(log n)d) O(log log n)
User Avatar
0 votes
2 answers
655
When do floors and ceilings matter while solving recurrences?
every time while finding recurence solution (in CLRS book , page 88) a statement "Floors and ceilings usually do not matter when solving recurrences" but my doubt is when they matter ?
every time while finding recurence solution (in CLRS book , page 88) a statement "Floors and ceilings usually do not matter when solving recurrences" but my doubt is whe...
User Avatar
14 votes
5 answers
656
How to find the complexity of T(n)=T(sqrt(n)) + 1 ?
Please tell me the complete steps how to solve this problem. $ T(n) = T ( \sqrt n )+ 1$
Please tell me the complete steps how to solve this problem.$ T(n) = T ( \sqrt n )+ 1$
User Avatar
0 votes
1 answer
657
Time complexity
T(n+1)=T(n)+ceil[√(n+1)] , n>1 =1,n=1
T(n+1)=T(n)+ceil[√(n+1)] , n>1 =1,n=1
User Avatar
0 votes
1 answer
658
Recurrence
T(n)=√nT(√n)+√n , n>2 =2 ,n=2
T(n)=√nT(√n)+√n , n>2 =2 ,n=2
User Avatar
1 votes
1 answer
659
common data Linked quetion :- 1) which of the following is correct recurrence formula of I(j) 2)how to evaluate this R.R
At the end of it's 5th Successful season,The siruseri Permier league is planning to give an award to most improved bowler over 5 years . For this an important Index will ...
User Avatar
Page: