Define big-oh, big-omega and big-theta in terms of time complexity of an algorithm. How they are related to each other. 1. Constant factor like in (n2-n) are ignored in O (big-oh) notation. 2. Prove that log (log ) a b n O n and log (log ) b a n O n 3. Show that if f(n)=2n + n 2 and g(n)= 2n then f n O g n ( ) ( ( ) 4. Let 3

( ) 2 n f n = and 2 g n n n ( ) 37 120 17 = + + then show that g n o f n ( ) ( ( )) 5. Let 2 f n n ( ) = and g n n n ( ) log = then show that f n O g n ( ) ( ( )) 6. Let

2 ( ) 2n f n n = + and ( ) 2n g n = then show that f n O g n ( ) ( ( ))

Define big-oh, big-omega and big-theta in terms of time complexity of an algorithm. How they are related to each other. 1. Constant factor like 1/2 in 1/2(n2n) are ignored in O (big-oh) notation. 2. Prove that loganO(logbn) and logbnO(logan) 3. Show that if f(n)=2n+n2 and g(n)=2n then f(n)O(g(n) 4. Let f(n)=2n3 and g(n)=37n2+120n+17 then show that g(n)o(f(n)) 5. Let f(n)=n2 and g(n)=nlogn then show that f(n)/O(g(n)) 6. Let f(n)=2n+n2 and g(n)=2n then show that f(n)O(g(n)) Define big-oh, big-omega and big-theta in terms of time complexity of an algorithm. How they are related to each other. 1. Constant factor like 1/2 in 1/2(n2n) are ignored in O (big-oh) notation. 2. Prove that loganO(logbn) and logbnO(logan) 3. Show that if f(n)=2n+n2 and g(n)=2n then f(n)O(g(n) 4. Let f(n)=2n3 and g(n)=37n2+120n+17 then show that g(n)o(f(n)) 5. Let f(n)=n2 and g(n)=nlogn then show that f(n)/O(g(n)) 6. Let f(n)=2n+n2 and g(n)=2n then show that f(n)O(g(n))