Recitation 11 (b)Indicate which of the following holds for each pair of functions f(m),g(n)in the table below;k> 1,E>0, and c>l are constants. Be prepared to justify your answers f(a)9G)f=oo|=o|9=O|g=o)f=6o|f~9 2 SIn n7 log(n! )log(n") Solution f(m)g(n)f=O(g)f=o(g)g=o9=0f=6(gf~g log(n!) log(n yes Following are some hints on deriving the table above (a)on/2 2n/ grows without bound as n grows-it is not bounded by a constant (b) When n is even, then n sinn/2= 1. So, no constant times n sin n /2 will be an uppe bound on Vn as n ranges over even numbers. When n= l mod 4, then nsin nr/> n=n. So, no constant times Vn will be an upper bound on nsin n/ as n ranges oⅴ er numbers≡1mod4. log(nl!)=logv2丌n +n(logn-1)±dn n where a≤cn,dln≤ b for some constants a,b∈ R and all n. equation(1) follows by taking logs of Stirlings formula, (2) follows from the fact that the log of a product is the sum of the logs, and(3)follows because any constant, log n, and are all o(n log n) and hence so is their sum (d)Polynomial growth versus exponential growth (e) Polylogarithmic growth versus polynomial growth� � Recitation 11 4 (b) Indicate which of the following holds for each pair of functions f(n), g(n) in the table below; k ≥ 1, � > 0, and c > 1 are constants. Be prepared to justify your answers. f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f = Θ(g) f ∼ g 2n 2n/2 √n nsin nπ/2 log(n!) log(nn) nk cn logk n n� Solution. f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f = Θ(g) f ∼ g 2n 2n/2 no no yes yes no no √n nsin nπ/2 no no no no no no log(n!) log(nn) yes no yes no yes yes nk cn yes yes no no no no logk n n� yes yes no no no no Following are some hints on deriving the table above: 2n (a) 2n/2 = 2n/2 grows without bound as n grows—it is not bounded by a constant. (b) When n is even, then nsin nπ/2 = 1. So, no constant times nsin nπ/2 will be an upper sin nπ/2 bound on √n as n ranges over even numbers. When n ≡ 1 mod 4, then n = 1 n = n. So, no constant times √n will be an upper bound on nsin nπ/2 as n ranges over numbers ≡ 1 mod 4. (c) log(n!) = log √ 2πn n e n ± cn (1) = log n + n(log n − 1) ± dn (2) ∼ n log n (3) = log nn. where a ≤ cn, dn ≤ b for some constants a, b ∈ R and all n. Here equation (1) follows by taking logs of Stirling’s formula, (2) follows from the fact that the log of a product is the sum of the logs, and (3) follows because any constant, log n, and n are all o(n log n) and hence so is their sum. (d) Polynomial growth versus exponential growth. (e) Polylogarithmic growth versus polynomial growth