4. (12 points): Analyze the following function in terms of time complexity: long

Question

4. (12 points): Analyze the following function in terms of time complexity: long int Fibonacci(int N) (N0)) if ((N 1) return 1; return (Fibonacci(N-1) + Fibonacci(N-2)) 4(a) (6 points): Complete the following table where Fibonacci) should represent the number of calls to the Fibonacci function for any given value of N. Also fill in the table with data corre- sponding to the other functions of N NFibonacci(O N! 2 4 4 24 120 720 5040 40320 362880 3628800 4. 10 4(b) (2 points): Based on the data of the table above, what is the time complexity of Fibonacci() in 0 () notation? Explain your reasoning. Recall that 0() is a "tight" upper bound on the complex- ity of an algorithm

Explanation / Answer

Hey,

Below are the answers to your question

4)

It can be seen that T(n)=T(n-1)+T(n-2) gives an exponential upper bound of O(2^n)

4.1)

1       1       1       2       1
2       3       2       4       4
3       5       6       8       9
4       9       24      16      16
5       15      120     32      25
6       25      720     64      36
7       41      5040    128     49
8       67      40320   256     64
9       109     362880 512     81
10      177     3628800 1024    100

4.2)

We can test the Fibonacci() value and compare with x^n. By which we will get x=0.16180

So, tight upper bound is O(0.16180)^n

4.3)

Kindly revert for any queries

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.