MATH 211 Problems, Fall 2010

AMERICAN UNIVERSITY OF BEIRUT Mathematics Department MATH 211 - Worksheet Fall 2010-2011 1) Show that (n + a)b = O(nb) for any real number a and positive whole number b. 2) Is 5n+1 = O(5n)? Is 5n+n = O(5n)? 3) Are there any functions that are not comparable using growth of functions notation? 4) page 192 exercise 36 5) page 192 exercise 39 6) Show that n log n is O(log n!). 7) Show that log n! is Θ(n log n). 8) Show that ⌈ln n⌉ is Θ(ln n). 9) Complete the following with the appropriate notation. f is bounded above by g (up to constant factor) asymptotically means ........... f is bounded below by g (up to constant factor) asymptotically means ........... f is bounded both above and below by g (up to a constant factor) asymptotically means ........... 10) Homework due Wed., Dec.15, 2010 (beginning of class) Answer by yes or no. Justify. (k ⩾ 1, c > 1, k′ > 0) A B Is A=O(B)? Is A=Ω(B)? Is A=Θ(B)? log(n!) log(nn) nlog c clog n 2n 2n/2 nk ck logk n nk′ en 2n