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

(a)

5n² - 6n < 5n² for n >= 1. So, 5n² - 6n = O(n²). Also, 5n² - 6n >= 5n² - n² = 4 n² for n >= 6. So, 5n² - 6n = Omega(n²). Consequently, 5n² - 6n = Theta(n²).

(c)

f(n) = 2n²2ⁿ + n log n < 2n²2ⁿ + n² < 3n²2ⁿ for n >= 1. So, f(n) = O(n²2ⁿ). Also, f(n) >= 2n²2ⁿ for n >= 1. So, f(n) = Omega(n²2ⁿ). Therefore, f(n) = Theta(n²2ⁿ).

(e)

f(n) = sum from (i=0) to n i³ <= sum from (i=1) to n n³ = n⁴ for n >= 1. So, f(n) = O(n⁴). Also, f(n) >= sum from (i=ceil(n/2)) to n i³ >= sum from (i=ceil(n/2)) to n (n/2)³ = (n - ceil(n/2) + 1)(n/2)³ >= n⁴/16 for n >= 1. So, f(n) = Omega(n⁴). As a result, f(n) = Theta(n⁴).

(g)

f(n) = n³ + 10⁶n² <= n³ + n³ = 2 n³ for n >= 10⁶. Also, f(n) < n³ for n > 0. So, f(n) = Theta(n³).