Register

Recurrence relation

• retagged by
558 views
0 votes
0 votes
Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.
Find the same for binary strings.

Also write the initial conditions.
• retagged by
User Avatar

1 Answer

0 votes
0 votes
Are we have to write recurrance relation or regular  expression? check the question please
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
Jaspreet Kaur Bains asked Dec 19, 2017
2,153 views
recurrence relation
Which recurrence relation satisfy the sequence: 2, 3, 4, . . ., for n ≥ 1. A ) T(N) = 2 T(N-1) - T(N-2) B)T(N) = T(N-1) + T(N-2) C)T(N) = N+1 D) None of these
Which recurrence relation satisfy the sequence: 2, 3, 4, . . ., for n ≥ 1.A ) T(N) = 2 T(N-1) - T(N-2) B)T(N) = T(N-1) + T(N-2)C)T(N) = N+1D)None of these
User Avatar
1 votes
1 votes
1 answer
2
jenilS7 asked Mar 18
129 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
0 votes
0 votes
1 answer
3
vivek1211 asked Oct 2, 2023
262 views
solve this recurrence relation
T(n) = T(n^1/2) + n doing this in substitution method gives the ans as O(n) but using tree recursion gives the ans as O(nlogn) which of these are correct and which has to be considered for worst case
T(n) = T(n^1/2) + ndoing this in substitution method gives the ans as O(n)but using tree recursion gives the ans as O(nlogn)which of these are correct and which has to be...
User Avatar
0 votes
0 votes
0 answers
4
rexritz asked Aug 13, 2023
303 views
How to solve the following recurrence relation? I get confused when decimals are used in the expression.
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
User Avatar
Link Copied!