P4. Suppose that f(N) >0 for all N0. Suppose that g(N) f(N)/2+ VN. For each of the following, specify if it is "definitely true", "definitely false", or "possibly true and possibly false". Justify your answer (using limits or other properties). If you answer "possibly true and possibly false", provide at least one specific example of f(N) that makes the answer "true" and one specific example of f(N) that makes the answer "false". a) f(N) O(g(N) b) f(N) 0(g(N) c) f(N) Q(g(N) P5. Let A [9, 5, 1, 3, 2, 7]. After 3 complete passes of insertion sort (3 iterations of the outer loop) the partially sorted array A is now: [1, 2, 3, 9,5, 7] Is the above statement true or false? Justify your answer // Insertion sort pseudo-code provided for reference. for 1: Jkey ii-1 A [ i+1] -key P6. a) Write code or pseudo-code for insertion sort. b) Given the array below, show how it is being processed by insertion sort (as described by you above). In particular, on each row, fill in the values of the array at the end of the outer loop of insertion sort. 4 9 16 11 0 7 After the first execution of the outer loop. After the second execution of the outer loop After the third execution of the outer loop. .(and so on) c) Show the array after each iteration of the inner loop P7. Show the array, A, at the end of each iteration of the outer loop of selection sort. Index: 0 1 1 4 Original Array: 0 P8. Give a piece of code with nested loops that has time complexity NIgN P9. 5N3N(N) True or False? Justify your answer. P10.5NN'(N) True or False? Justify your answer. P11. Given summation: 1 + 26 + 36+ + N6 Can you solve this in terms of , or 0 ? P12. Below is the code for selection sort. There was a suggestion in class for making it stable. Based on that suggestion or your own ideas, modify this algorithm to become stable. (The modified algorithm can behave somewhat different than selection sort, but it should still place the j-th smallest element its final position, j, after the j-th iteration of the outer loop.)<-1:>