I'm having a little trouble figuring out how to approach this. I have some ideas but please let me know if you think I'm on the right track. If not how would you approach it?

a) I was thinking of showing this by displaying a tree, do you guys think that would be sufficient? I feel like there's a way to prove it mathematically.

b) If we implement it in say, an array or some other way to save our information then all we would have to do is traverse the array twice. Once for n and once for n-1. This will give us an array of (n)*(n-1) => n^2-n => O(n^2). Too simple?

c) No idea...

. Consider the recurrence relation T(0) T()-2 and for n>1 We consider the problem of computing T(n) from n. (a) Nave method: Show that if you implement this recursion directly in say the Java programming language, then the program would use exponentially, in n, many arithmetic operations. (b) Memoization: Explain how, by not recomputing the same T(i) value twice, one can obtain an (c) Dynamic programming: Give an algorithm for this problem that only uses O(n) arithmetic operations. (Hint: Subproblems are T(i) where Ti)- T()T(i 1).) . Consider the recurrence relation T(0) T()-2 and for n>1 We consider the problem of computing T(n) from n. (a) Nave method: Show that if you implement this recursion directly in say the Java programming language, then the program would use exponentially, in n, many arithmetic operations. (b) Memoization: Explain how, by not recomputing the same T(i) value twice, one can obtain an (c) Dynamic programming: Give an algorithm for this problem that only uses O(n) arithmetic operations. (Hint: Subproblems are T(i) where Ti)- T()T(i 1).)