Show the following: = n(n+1)/2. = n(n+1)(2n+1)/6. What about , where k is a positive integer? See also problem 6 below. Consider the following functions:
Show the following: = n(n+1)/2. = n(n+1)(2n+1)/6. What about , where k is a positive integer? See also problem 6 below. Consider the following functions: f1(n) = n2. f2(n) = n2 + 10000n. f3(n) = n, if n is odd, = n3, if n is even. f4(n) = n, if n 1000, = n3, if n > 1000. Answer whether fi (n) is O(fj (n)) and whether fi (n) is (fj (n)) for each distinct pair i and j. Consider the following functions: g1(n) = n2, if n is even, = n3, if n is odd. g2(n) = n, if 0 n 1000, = n3, if n > 1000. g3(n) = n2.5 Answer whether gi (n) is O(gj (n)) and whether gi(n) is (gj(n)) for each distinct pair i and j. Show that n log n –n + 1 (n + 1) log (n + 1) – n + 1 – 2log2, where the base of the logarithms is e. Hence, is (n log n). How does the above formula change if the base of the logarithms within the summation sign is 2 Give, using “big oh” notation, the worst case running times of the following procedures as a function of n ≥ 0.
