Question

1. For each of the following, prove using the definition of O): (a) 7n + log(n) = O(n) (b) n2 + 4n + 7 =0(na) (c) n! = ((n") (d) 21 = 0(221)

Answer 1

From definition of Big O

f(n) = O(g(n))

if f(n) <= g(n)

a)

f(n) 7n log(n)= (n) g(n) f(n) = O(n)

b)

g(n) (n2) f(n)n24n7 e(n)g(n) f(n) - O(n2)

c)

g(n) = (n") f (n) n!(n!) f(n)O(n") g(n)

d)

g(n) (22n) f (n) ) 2" e(2") g(n) f(n) O(22n)

Answer 2

1. a) Let us say f(n) = In + log (n). In + log(n) € In +n I As we knowe, nylog(n)] In + log(n) = 8 - In + log(n) {con If nyno, where no=1 and for some positive constant e=8 Hence, by defination of o-notation: - os fin) sein = f(n) = 0(1) - In + log(n) = 0 (n) I proved]

1.6) Let us say, f(n) = n²+40 +7. i n+40 +7 £n²+ 40 + 1n? 7 L Int [As 4n < 4n² & I na - nt+4n+ 7 L 12n?. => nt tan +7 Çe.nz V nno whone no= 1 and et c=12 is a positive. constant o-notation Herce, by defination of os fin) Len² - f(n) = 0(ne) + m2+42 + 7 = O(n) [proved] Le Let us say f(n) = n! 1.d) - T = n = (- ) ( x-2). 12x12 nx x x xn 7 times n! Ene & nono, where not Hence, by detination of O- notation os f(n) < c.nn [ whene cas a positive constant => f(n) = 0(1) = n! =02") [ proved] Let us say, fin) = 22. i 2n <2 2 2 220 vntno, whene no=0 2n<2in [ AS 152nr no implies 242.2 vnzo]. Herce, by defination of o-notation:- oç f(n) < c.220 [where et a positive. constant - f(n) = 0 (22) => 2n = 0(229) [proved]
The answers for the following questions are given as handwritten notes.