Claim Justification 0. f(n) E O(g(n)) if there exist non-negative Definition of O(.). constants n and c such that o s f(n) s cg(n) for alln 2 n. 1. Consider n = 10. Introduction of no 2. Consider any n 2 n. Introduction of n 3. n + 10 2n + 10. Adding 10 to both sides of (2) 4. n + 10 2 20 2 0. Substituting (1) into (3), arithmetic 5. n + 10 = n + n. Substitution of n = 10 6. n + 10 S n + n. Applying (2) to (3) 7. n + 10 0, X be a non-negative random variable. Then, for every constant 6 > 0, Pr(X E(X) 2 55m) 5 This means that if you introduce a large enough 6, then probability that the actual value of X exceeds 6E(X) can be quite small. In the following problem, we'll see some strengths and weaknesses of the inequality.6, then probability that the actual value of X exceeds (SET-X) can be quite small. In the following problem, we'll see some strengths and weaknesses of the inequality. Problem 3: You work for a company looking to hire programmers. You want to hire the best person for the job, but you don't want to end up with a situation where you potentially have to hire everyone. Assume that you have a list of candidates of length n. 1. Under the old strategy of always hiring the best person, how many hires would you need to make before the probability that you hire nobody new decreases below '/3? Under the old strategy of always hiring the best person, how many hires can you make while the probability that you will still hire someone new remains more than 3'3? Suppose you're comfortable hiring someone who isn't the best, but only with some small probability P . Write pseudocode for an algorithm that hires at most O(log(n)) employees and hires the best one with probability 1 P , where P is considered as a constant. Express the runtime of your algorithm as a function of both 11. and the parameter P. (You could imagine a case where the P you care about changes with n, so it is good to explicitly show how 00 depends on P.)