Google Exercise 1 (3 pts). Consider an algorithm A with rung time nvn. Assume that A can solve instances of size n on a machine that takes 1012 seconds per operation. What size instances (in terms of n) can A solve in the same time on a machine that takes 10-15 seconds per operation? Exercise 2 (1 pt). Is 2+100O(2")? Why? Exercise 3 (1 pt). Is 22n-0(2")? Why? Exercise 4 (1 pt). Is lg100 n (no.01)? Exercise 5 (1 pt). Give an example of functions f(n) and g(n) such that f(n) - O(g(n)), but f(n) fo(g(n)) Exercise 6 (3 pts). In each of the following situations, indicate whether f - O(g), or f-S2(g), or both (in which case f-6(g): f (n) 110n Vn2n + (lg n) 2 n lg n g(n) either O, or . or 10n lg(10n2) nlg n) g(10n TL Il Exercise 7 (3 pts). Order the following functions according to their order of growth (from the lowest to the highest): n, lg n Bonus Exercise 8 (3 pts). What is the relationship (in terms of asymptotic growth) between n lgn and n sin n