C. Prove the following (you can use any formal induction/other theoretical method, A means power here):...

Transcribed Image Text:

C. Prove the following (you can use any formal induction/other theoretical method, "A" means power here): i. ii. iii. What is the time complexity recurrence relation for Fibonacci numbers? Explain it with the subproblems and size of sub-problems. Show the time complexity derivation using the telescoping method. (4 marks) Show that 2n^3+5n^2+6n+ 18 is in Theta (n^3). (2 marks) 5+2cos(n) Theta (1) (2 marks) iv. Show that (3/2)n^2+2n-3 = 2 (n^2) (2 marks) V. Show that n^3+5n is not O(n^2) (2 marks). vi. vii. T(n) = 2T (n/2)+n = O(n) (2 marks) T(n)T(n/4)+T(5n/8) n = O(n) (2 marks) C. Prove the following (you can use any formal induction/other theoretical method, "A" means power here): i. ii. iii. What is the time complexity recurrence relation for Fibonacci numbers? Explain it with the subproblems and size of sub-problems. Show the time complexity derivation using the telescoping method. (4 marks) Show that 2n^3+5n^2+6n+ 18 is in Theta (n^3). (2 marks) 5+2cos(n) Theta (1) (2 marks) iv. Show that (3/2)n^2+2n-3 = 2 (n^2) (2 marks) V. Show that n^3+5n is not O(n^2) (2 marks). vi. vii. T(n) = 2T (n/2)+n = O(n) (2 marks) T(n)T(n/4)+T(5n/8) n = O(n) (2 marks)