1. Using the definition of limit to show that if limn!1 f(n) g(n) = 1, then f(n) = !(g(n)). 2. Suppose f(n) is a positive increasing function defined for natural numbers n = 1, 2, ... Now assume that we can prove when n is a power of 2 (i.e., n = 2k for k = 0, 1, ...), there exists positive constants c and n0 such that for all n " n0, f(n) " cn. Is this su!cient for claiming that f(n) = O(n)? 3. Sort the following functions based on their asympotic growth rate. f(n) = 10#10, g(n) = 1010, n2, (log2 n)2, 2n, 3n, n log2 n, log2 n, log3 n, 2log2 n, (p2)log2 n, (log2 n)log2 n, nlog2 n, pn, log2 pn, log2 (log2 n), nn(1 + ($1)n). 4. Verify using mathematical induction that Fn = 1 p5 0 @ 1 + p5 2 !n+1 $ 1 $ p5 2 !n+11 A is the solution to the recurrence relation: 8 >< >: Fn = Fn#1 + Fn#2 for n " 2 F1 = 1 F0 = 1 5. Use both the charateristic equation method and the generating function method to find an analytical solution to the following Fiboncci sequence with di↵erent intial values: 8 >< >: Fn = Fn#1 + Fn#2 for n " 2 F1 = 1 F0 = 0 6. Solve the following non-homogeneous congruence relation: ( an = 3an#1 + 2 for n " 2 a0 = 0 7. Consider a special type of tree data structure over the universe {0, 1, ..., n $ 1}. Each node of this tree has O( pn) children. Let these children be indexed 0, 1, ..., pn $ 1, where the j$th child is responsible for storing the keys within the range {j pn, ...,(j + 1)pn $ 1}. What is the maximum height this type of tree? 8. In computational geometry, an arrangement of lines is the partition of the plane formed by a collection of lines. Observe that the lines partition the plane into disjoint regions. Calculate the maximum number of disjoint regions in an arragement created by n lines. 9. Use the recursion tree method to determine a good upper bound on the recurrence