Please show all work for my understanding. Please write the extra credit short program in Java. Thanks!

Suppose you have algorithms with the three running times listed below. (Assume these are the exact running times.) How much slower do each of these algorithms get when you (a) double the input size; or (b) increase the input size by one? (So you should give two answers for each of the three.) For some functions, you might show the answer in terms of a ratio; for others, in terms of a difference. Assume that all logs are base two. (1) f(n)=31n2+4 (2) f(n)=2n+n (3) f(n)=nlogn For (1a), derive an expression for f(2n)f(n); for (1b), derive an expression for f(n+1)f(n). For (2a), derive an expression for f(2n)f(n); for (2b), derive an expression for f(n+1)f(n). For (3a), write the expression for f(2n)/f(n) and simplify it as much as you can; for (3b), look at f(n+1)f(n) and go as far as you can. For six points. For full credit, show your work. Don't just use Wolfram Alpha. Suppose you have algorithms with the three running times listed below. (Assume these are the exact number of operations performed as a function of the input size n.) Suppose you have a computer that can perform 106 operations per second, and you need to compute a result in at most ten minutes of computation. For each of the algorithms, what is the largest input size n for which you would be able to get the result within ten minutes? (a) g(n)=2n(logn) (b) g(n)=(n!) (c) g(n)=(nk), for k=4; and then for k=6. Recall that (nk)=k!(nk)!n! 1 Graduate students and undergraduates for a little extra credit: in addition, for each of these three functions, write a program to find the value of n in each case such that we could compute a result for a problem of size n in the minutes, but for which a problem of size n+1 could not be computed in the permitted time. Submit your programs as well as your solution. (It's OK to put all three in a single program.)