Register

algorithm-recurrence relation

• edited by
335 views
0 votes
0 votes
How to write  recurrence relation for , possible binary sequence of size n ?
• edited by
User Avatar

1 Answer

Best answer
2 votes
2 votes
here by size means by length n

so minimum 1 bit we can represent 0 or 1 total 2 elements

form 2 bit we can represent 00,01,10,11  total 4 element

so

T(n) = $\left\{\begin{matrix} 2T(n-1) & n>1 \\ 2 & n=1 \end{matrix}\right.$
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

927
views
2 answers
1 votes
srestha asked May 10, 2019
927 views
Made Easy Test Series:Algorithm-Recurrence Relation
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
User Avatar
11.5k
views
3 answers
1 votes
Vivek Jain asked Apr 20, 2016
11,469 views
The recurrence relation for MAX-HEAPIFY function of heapsort algorithm is T(n) <= T(2n/3) + O(1). How is it 2n/3 ?
User Avatar
196
views
1 answers
1 votes
jenilS7 asked Mar 18
196 views
Recurrence relation
What is the returned value by the given function below.Algo fun(n){ If(x<=2) return 1; Else { Return fun(n1/2) + n; }}Note : Assume that all...
User Avatar
657
views
0 answers
1 votes
srestha asked May 19, 2019
657 views
Recurrence Relation-Self Doubt(Discrete Math+Algo)
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
User Avatar
Link Copied!