Analyze the following piece of pseudocode and give a tight (C) bound on the running time as a function of n. Show your work. A formal proof is not required, but you should justify your answer (in all cases, n is assumed to be a positive integer). a x = 0 for i = 1 to n * n * n do for j = 1 to i * i do x = x * 2 b) x = 1 y = 0 for i = 1 to n do x = x * 5 for j = 1 to x do y = y + 1 c) x := -42 y := 1 while y y do x := 2 - x z := z - y y := y + 5 d) Consider the following (rather strange) code-fragment: mystery (int n) { // pre: n >= 2 compute L := floor( log (n) ). if L is even print all subsets of {1,...,L} else print all subsets of {1,...,2L} For example, for n = 17, we have L = (log(17)] = 4, so the code prints all 16 subsets of {1, 2, 3,4}. Let f(n) be the run-time of this code. You may assume that computing log(n) takes O(1) time, and printing the subsets of {1,..., k} takes O (2k) time. i) Find a constant d and prove that f(n) E O(nd). Your d should be as small as possible, but you need not prove that it is minimal. ii) Find a constant d2 and prove that f(n) E N(nd2). Your d2 should be as big as possible, but you need not prove that it is maximal. iii) Bonus: Argue that there cannot exist a constant d such that f(n) O(n^)