Register

Recent questions tagged recurrence-relation

0 votes
2 answers
241
Kenneth Rosen Edition 6th Exercise 7.1 Question 23 (Page No. 458)
Find a recurrence relation for the number of bit strings of length n that contains a pair of consecutive 0s
Find a recurrence relation for the number of bit strings of length n that contains a pair of consecutive 0s
User Avatar
1 votes
2 answers
242
#discrete matmatics
recurrence relation 2a$_{n}=a_{n-1}+2^{n}$ intial condtion a$_{0}$=1 value of a$_{100}$
recurrence relation 2a$_{n}=a_{n-1}+2^{n}$ intial condtion a$_{0}$=1 value of a$_{100}$
User Avatar
0 votes
1 answer
243
Kenneth Rosen Edition 6th Exercise 6.1 Example 7 (Page No. 399)
this is an example taken from Rosen. but I’m unable to understand to understand the solution given there can someone pls explain me in details
this is an example taken from Rosen. but I’m unable to understand to understand the solution given therecan someone pls explain me in details
User Avatar
0 votes
0 answers
244
SELF DOUBT GENERATING FUNCTION
Difference between getting closed form of generating function and closed form of the given sequence ,pls someone explain with an example
Difference between getting closed form of generating function and closed form of the given sequence ,pls someone explain with an example
User Avatar
0 votes
3 answers
245
NIELIT 2018-75
For the given recurrence equation $\begin{array} T(n) & =2T(n-1), &\text{if } n>0 \\ & =1, & \text{otherwise} \end{array}$ $O(n \log n)$ $O(n^2)$ $O(2^n)$ $O(n)$
For the given recurrence equation$\begin{array} T(n) & =2T(n-1), &\text{if } n>0 \\ & =1, & \text{otherwise} \end{array}$$O(n \log n)$$O(n^2)$$O(2^n)$$O(n)$
User Avatar
0 votes
0 answers
247
Doubt : Recurrence Relation.
T(n)=T(n-1)*(n-1)+1 hints : define R(n) = T(n)/(n-1)! solve the recurrence for R(n) express T(n) as a function of R(n) How to proceed , i am not getting it ? Can i reduce it to the form so that i can use masters theorem.
T(n)=T(n-1)*(n-1)+1 hints :define R(n) = T(n)/(n-1)!solve the recurrence for R(n)express T(n) as a function of R(n) How to proceed , i am not getting it ?Can i reduce it ...
User Avatar
0 votes
1 answer
248
#time complexity
T(n)=4T(n/2)+n$^{2}\sqrt{2}$ T.C
T(n)=4T(n/2)+n$^{2}\sqrt{2}$ T.C
User Avatar
0 votes
0 answers
249
ace academy test series
Please explain in some detail.
Please explain in some detail.
User Avatar
4 votes
2 answers
251
T(n) = sqrt(n) * T(sqrt(n)) + n
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n). 'wolframalpha'' shows the answer same as mine. You can find the solution here. Can anyone confirm the solution and provide an explantion?
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n).'wolframalpha'' shows the answer same as mine. You can find the solution...
User Avatar
0 votes
0 answers
252
SELF DOUBT MADEESY TEST
WHAT IS RECURRENCE RELATION ? I M GETTING T(n-2)+1
WHAT IS RECURRENCE RELATION ?I M GETTING T(n-2)+1
User Avatar
0 votes
1 answer
253
recurrence relation
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
T(n)=5 T ($\frac{n}{2}$+16) + n2please tell the solution as i m getting confused
User Avatar
0 votes
0 answers
254
Time Complexity
How to solve the following recurrence relation? T(n) = T(n-6) + n2 , n>7 T(n) = 1 , n<= 7
How to solve the following recurrence relation?T(n) = T(n-6) + n2 , n>7T(n) = 1 , n<= 7
User Avatar
1 votes
1 answer
255
What is the value of T(n) for the given recurrence relation
T(n)=T(n/2)+2; T(1)=1 when n is power of 2 the correct expression for T(n) is: a) 2(logn+1) b) 2logn c)logn+1 d)2logn+1
T(n)=T(n/2)+2; T(1)=1when n is power of 2 the correct expression for T(n) is:a) 2(logn+1)b) 2lognc)logn+1d)2logn+1
User Avatar
0 votes
1 answer
256
test series - Testbook
Which of the following functions given by their recurrences grows the fastest asymptotically? $T(n) = 8T(n/4) + 100n^2$ $T(n) = 81T(n/9) + 10n^2$ $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$ $T(n) = 100T(n/100)+ n \log^2 n$
Which of the following functions given by their recurrences grows the fastest asymptotically?$T(n) = 8T(n/4) + 100n^2$$T(n) = 81T(n/9) + 10n^2$$T(n) = 16T(n/4)+ 100(n \lo...
User Avatar
0 votes
1 answer
257
Self Doubt
What is order of T(n) ? T(n) = T(n-1) + 2$^{n}$ , n>1 T(n) = 1 , n=1 A) O(2$^{n}$) B) O(n.2$^{n}$) C) O(2$^{2n}$)
What is order of T(n) ?T(n) = T(n-1) + 2$^{n}$ , n>1T(n) = 1 , n=1A) O(2$^{n}$)B) O(n.2$^{n}$)C) O(2$^{2n}$)
User Avatar
0 votes
2 answers
259
Karumanchi
User Avatar
0 votes
1 answer
260
recurrence equation:
T(1) = 1 T(n) = 2T(n - 1) + n, n ≥ 2 evaluates to (a) 2n + 1 - n – 2 (b) 2n – n (c) 2n + 1 – 2n – 2 (d) 2n – n HOW TO EVALUATES USING MASTER THEOREM
T(1) = 1 T(n) = 2T(n - 1) + n, n ≥ 2 evaluates to(a) 2n + 1 - n – 2(b) 2n – n(c) 2n + 1 – 2n – 2(d) 2n – n HOW TO EVALUATES USING MASTER THEOREM
User Avatar
0 votes
1 answer
261
Recurrence Relations
Given $T(n)=T(\frac{n}{4})+T(\frac{n}{2})+n^{2},$ then $A)T(n)=\theta(n^{3})$ $B)T(n)=\theta(n^{2}logn)$ $C)T(n)=\theta(n^{2})$ $D)T(n)=\theta(n^{3}logn)$
Given $T(n)=T(\frac{n}{4})+T(\frac{n}{2})+n^{2},$ then$A)T(n)=\theta(n^{3})$ $B)T(n)=\theta(n^{2}logn)$ $C)T(n)=\theta(n^{2})$ ...
User Avatar
0 votes
1 answer
263
Analysis of algorithms of recurrence relation
I want to learn to find time complexity of the recurrence relation of an algorithm. Please suggest some good links or any gatetoverflow imp questions links to look as examples . Thanks
I want to learn to find time complexity of the recurrence relation of an algorithm.Please suggest some good links or any gatetoverflow imp questions links to look as exam...
User Avatar
1 votes
1 answer
264
Time Complexity
how to compute time complexity of this kind of recurrence relation- T(n)=T(n/2)+T(n/4)+T(n/8)+n
how to compute time complexity of this kind of recurrence relation-T(n)=T(n/2)+T(n/4)+T(n/8)+n
User Avatar
0 votes
1 answer
266
Quick Sort
In Quicksort let n/7​ th ​ smallest element is chosen using an O(n2​ ) algorithm as the pivot. Calculate the worst case time complexity of the algorithm.
In Quicksort let n/7​ th ​ smallest element is chosen using an O(n2​ ) algorithm as thepivot. Calculate the worst case time complexity of the algorithm.
User Avatar
0 votes
3 answers
267
Merge Sort Doubt
what is the recurrence relation for merge sort?
what is the recurrence relation for merge sort?
User Avatar
0 votes
2 answers
268
Recurrence Relation
Let $T(n) = T(n-1) + \frac{1}{n} , T(1) = 1 ;$ then $T(n) = ? $ $O(n^{2})$ $O(logn)$ $O(nlogn)$ $O(n^{2}logn)$
Let $T(n) = T(n-1) + \frac{1}{n} , T(1) = 1 ;$ then $T(n) = ? $$O(n^{2})$$O(logn)$$O(nlogn)$$O(n^{2}logn)$
User Avatar
0 votes
1 answer
269
Homework
T(n)=0.5T(n/2)+n^3 How to solve this using recurrence method?
T(n)=0.5T(n/2)+n^3How to solve this using recurrence method?
User Avatar
5 votes
3 answers
270
recurrence relation MIT
$T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this.
$T(n)=\sqrt{n} T(\sqrt{n})+100n$Please solve this.
User Avatar
Page: