Consider the sequence a1, A2, A3, , ao defined as follows. = 0, a1 = =...

Transcribed Image Text:

Consider the sequence a1, A2, A3, , ao defined as follows. = 0, a1 = = 0, a2 = 1, An1 + 2an2 + 3an3, n 3 and n is odd, = 3an 12an-2+ an3, n > 3 and n is even. Here are the first few terms of the sequence: 0, 0, 1, 1, 5, 10, 41, 76, 320, . . .. Give a linear time algorithm that takes as input an integer n and returns an. You must provide a formal proof of the correctness of your algorithm and an analysis of its running time. NOTE: The algorithm that keeps an array of size 3 to remember the last three numbers in the sequence and using a loop to compute an has a running time of O(n) which is clearly not a linear time algorithm. It's an exponential time algorithm. Consider the sequence a1, A2, A3, , ao defined as follows. = 0, a1 = = 0, a2 = 1, An1 + 2an2 + 3an3, n 3 and n is odd, = 3an 12an-2+ an3, n > 3 and n is even. Here are the first few terms of the sequence: 0, 0, 1, 1, 5, 10, 41, 76, 320, . . .. Give a linear time algorithm that takes as input an integer n and returns an. You must provide a formal proof of the correctness of your algorithm and an analysis of its running time. NOTE: The algorithm that keeps an array of size 3 to remember the last three numbers in the sequence and using a loop to compute an has a running time of O(n) which is clearly not a linear time algorithm. It's an exponential time algorithm.