Please show all work for my understanding. Please complete extra credit problem as well. Thanks!

1A)

1B)

For four points. Do this problem also: knowing that f(n) and g(n) are each O(h(n)) for some function h, show rigorously (using the definition of O() ) that f(n)+g(n) is also O(h(n)). Remember: f(n) is O(h(n)) if there exist c>0 and n00 such that for all nn0,f(n)ch(n). Students taking the course for graduate credit, and undergraduates for a little bit of extra credit: let f(n) be the runtime of some algorithm, and suppose that f(n+1)f(n)=f(n). What is f(n) ? Prove this. Then, suppose that g(n) is the runtime of some other algorithm, and g(2n)/g(n)=2. What is g(n) ? Prove this