In Corollary 10.2 we were concerned with finding the appropriate "big-Oh" form for a function f: Z+ †’ R+ U {0} where
f(1) ‰¤ c, for c ˆˆ Z+
f(n) ‰¤ af (n / b) + c,
for a, b ˆˆ Z+ with b ‰¥ 2, and n = bk, k ˆˆ Z+.
Here the constant c in the second inequality is interpreted as the amount of time needed to break down the given problem of size n into a smaller (similar) problems of size n/b and to combine the a solutions of these smaller problems in order to get a solution for the original problem of size n. Now we shall examine a situation wherein this amount of time is no longer constant but depends on n.
(a) Let a, b, c ˆˆ Z+, with b ‰¥ 2. Let b: Z+ †’ R+ U {0} be a monotone increasing function, where
F(1) ‰¤ c
f(n) ‰¤ af(n/b) + cn, for n = bk, k ˆˆ Z+.
Use an argument similar to the one given (for equalities) in Theorem 10.1 to show that for all n = 1,b, b2, b3, ...,

(b) Use the result of part (a) to show that f ˆˆ O (n log n), where a = b. (The base for the log function here is any real number greater than 1.)
(c) When a ‰  b, show that part (a) implies that

(d) From part (c), prove that (i) f ˆˆ O (n), when a b.

Transcribed Image Text:

k+1 k+1