Question

Mr. Blue Tiger wants to create his own version of fibonacci sequence. Since 3 is his favorite number, he decides that any element should be the sum of its previous three elements. Can you help him figure out the time complexity of his recursive function? Select All the answers that are correct, and state your reason. int TigerNacci (unsigned int n) { 2 if (n < 3) return 1; 3 return TigerNacci (n-1) + Tiger Nacci (n - 2) + TigerNacci(n − 3); i) (n³ log n) ii) (3" log n) iii) O(3" log n) iv) (3¹) v) (n² log n) vi) (2" log n) vii) O(2" log n) viii) (2¹¹) (a) Derive the recurrence relation of the TigerNacci function complexity. (Hint: Can you use master theorem here?) Solution: then find out its time

Answer 1

The time complexity of the TigerNacci function can be derived using the recurrence relation. Since the function is calculating the sum of the previous three elements, its recurrence relation is:

T(n) = T(n-1) + T(n-2) + T(n-3)

where T(n) is the time taken to calculate the nth element of the TigerNacci sequence.

Unfortunately, we cannot use the Master theorem directly to solve this recurrence relation because it is not in the form T(n) = aT(n/b) + f(n). However, we can try to guess the solution and then prove it using induction.

One possible guess is that T(n) = O(3^n). To prove this, we assume that T(k) <= c*3^k for all k < n (inductive hypothesis), where c is a constant. Then,

T(n) = T(n-1) + T(n-2) + T(n-3) <= c3^(n-1) + c3^(n-2) + c3^(n-3) (by inductive hypothesis) = c3^(n-3) * (3 + 1 + 1/3) = c3^(n-3) * 10/3 < c3^n (for c >= 10/3)

Therefore, we have shown that T(n) = O(3^n). This means that options (i), (ii), (iii), and (v) are incorrect because they have an asymptotic upper bound of less than 3^n. Option (iv) is also incorrect because it has a constant upper bound. Option (vi) is correct because it has an asymptotic upper bound of 2^n and 2 < 3. Option (vii) is also correct because it is equivalent to O(2^n). Option (viii) is incorrect because it has a constant upper bound. Therefore, the correct answers are (vi) and (vii).

Step-by-step explanation: