Register

algorithm-recurrence relation

• edited by
328 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

1 votes
1 votes
2 answers
1
srestha asked May 10, 2019
892 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$
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
User Avatar
1 votes
1 votes
1 answer
3
jenilS7 asked Mar 18
139 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 the syntax and data type constraints are valid and just check algorithm.
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
1 votes
1 votes
0 answers
4
srestha asked May 19, 2019
640 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 Complexity??
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!