Part B: Problem 2: Consider the following limit definition: Definition B-2.1: We say a function f has an infinite limit at infinity: lim f(n) = ∞ TL-00 If for all M > 0, there exists an N >0 such that f(n) > M for all n > N Answer the following questions: (a) Prove the following using the definition above (Definition B-2.1): f(n) If lim = ∞, then f(n) = N(g(n)) n-∞0 g(n) (b) What does this mean intuitively when analyzing algorithms? (c) Use limits to quickly show that n is a lower bound for n logn. (Evaluating the limit is sufficient. You do not need to use the precise definition above (Definition B-2.1).)

Part B: Problem 2: Consider the following limit definition: Definition B-2.1: We say a function f has an infinite limit at infinity: lim f(n) = ∞ TL-00 If for all M > 0, there exists an N >0 such that f(n) > M for all n > N Answer the following questions: (a) Prove the following using the definition above (Definition B-2.1): f(n) If lim = ∞, then f(n) = N(g(n)) n-∞0 g(n) (b) What does this mean intuitively when analyzing algorithms? (c) Use limits to quickly show that n is a lower bound for n logn. (Evaluating the limit is sufficient. You do not need to use the precise definition above (Definition B-2.1).)