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) = ∞ 004-2 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): If lim f(n) g(n) 004-2 = ∞, then f(n) = (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 log n. (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) = ∞ 004-2 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): If lim f(n) g(n) 004-2 = ∞, then f(n) = (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 log n. (Evaluating the limit is sufficient. You do not need to use the precise definition above (Definition B-2.1).)