Question 4 (a) Consider the following array: A: 5, 3, 7, 12, 2, 8, 4, 1 i. Using insertion sort, show A after one iteration (in ascending order). Show A after the second parsing. (Dmarks) ii. Using bubble sort show A after one iteration (in ascending order). Show A after the second parsing. iii. Give an instance of the best case input for the insertion sort. Explain your reasoning. (b) Design a Context-free Grammar for the following language: L= {W| No(W)>2 N1(W), W is a binary string}, No(W) shows the number of existing Os in W. For example, if W=10010 then No(W)=3 and N1 (W)=2 mars) (c) Assume f(n)=4n0.1, g(n)=10 log n, h(n)=2", p(n)=3log(n) i. Is the following statement correct? Why? f(n)=O(g(n)) ii. Is the following statement correct? Why? h(n)=O(p(n)) iii. Is the following statement correct? Why? g(n)=O(h(n)) (d) Design a Turing Machine that accepts the following language: L={anb"| n>0 and n is even} (e) Use the merge sort to sort the following list in ascending order. Show your work step by step. 7, 12, 34, 23, 16, 1, 14