Computer Sciences > Gate 2016 Set-1 > Recurrence Relation

Contributed by: Dr. Sarah Chen

Report Correct Copyright Claim

Let a_n be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for a_n?

A

a_n = a_n−1 +2a_n-2

B

a_n= a_n−1 +a_n-2

C

a_n= 2a_n−1 +a_n-2

D

a_n= 2a_n−1 +2a_n-2

Check Answer

Explanation

Correct : Recurrence Relation

Similar Questions

What is the worst-case time complexity of insertion in an AVL tree?

Question #23 Medium

Which operations on a binary search tree have O(h) complexity?

Question #31 Easy

Compare search complexities of sorted array vs balanced BST.

Question #47 Hard

Related Topics

Data Structures Binary Search Tree Time Complexity Algorithm Analysis Tree Algorithms Computer Science