Data Structures, Algorithms, & Applications in C++
Chapter 3, Exercise 10

(a)

(5n² - 6n) / n² = 5 - 6 / n which is <= 5. n² / (5n² - 6n) = n / (5n - 6) = 1 / (5 - 6 / n) which, in the limit, is <= 1 / 4. So, the function is Theta(n²).

(c)

f(n) / g(n) = 2 + (log n) / (n 2ⁿ) < 3. g(n) / f(n) = 1 / (2 + (log n / (n 2ⁿ)) <= 0.5. So, f(n) = Theta(g(n)).

(e)

f(n) / g(n) = [sum from (i=0) to n i³] / n⁴ <= [sum from (i=1) to n n³] / n⁴ = n⁴ / n⁴ = 1. Consider the case when n is even. g(n) / f(n) <= n⁴ / (sum from (i = n / 2 + 1) to n i³) < n⁴ / (sum from (i = n / 2 + 1) to n (n / 2)³) = n⁴ / (n⁴ / 16) = 16. The proof that g(n) / f(n) <= c when n is odd is similar. So, f(n) = Theta(g(n)).

(g)

f(n) / g(n) = 1 + 10⁶ / n <= 10⁶ + 1 and g(n) / f(n) <= 1. Hence, f(n) = Theta(g(n)).