Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 41

(a)

1. a = 10, b = 3, and g(n) = 11n.
2. logba = log310 > 2 and h(n) = 11n/nlog310 = O(nr) where r < 0. Therefore, f(n) = O(1).
3. t(n) = nlog310[t(1) + O(1)] = Theta(nlog310)

(c)

1. a = 27, b = 3, and g(n) = 11n3.
2. logba = log327 = 3 and h(n) = 11n3/n3 = 11 = Theta((log n)0). Therefore, f(n) = Theta(log n).
3. t(n) = n3[t(1) + Theta(log n)] = Theta(n3log n)

(e)

1. a = 9, b = 2, and g(n) = n22n.
2. logba = log29 < 4 and h(n) = n22n/nlog29 = Omega(nr) for some r > 0. Therefore, f(n) = Theta( n22n/nlog29).
3. t(n) = nlog29[t(1) + Theta( n22n/nlog29)] = Theta(n22n)

(g)

1. a = 128, b = 2, and g(n) = 6n.
2. logba = log2128 = 7 and h(n) = 6n/n7 = 6n-6. Therefore, f(n) = O(1).
3. t(n) = n7[t(1) + O(1)] = Theta(n7)

(i)

1. a = 128, b = 2, and g(n) = 2n/n.
2. logba = log2128 = 7 and h(n) = 2n/n/n7 = Omega(nr) for some r > 0. Therefore, f(n) = Theta(2n/n8).
3. t(n) = n7[t(1) + Theta(2n/n8)] = Theta(2n/n)