Question

1. Find the upper bound and lower bound constants for this function $T(n) = 5n^7 + n + 2n^2$ to show that it is in $\Theta(n^7)$.

2. To apply the Master's Theorem, the running time function is best expressed in this form $T(n) = \Theta(n^d) + a \cdot T({n \over b})$.

Rewrite this function $T(n) = 10n^2 + 5n + 1 + 3 \cdot T({n \over 4})$ in the form above.

Answer 1

The upper and lower bounds for the function T(n) can be found by comparing to cn⁷ and ignoring lower-degree terms for large n values, demonstrating it is in θ(n⁷). The function T(n) is already near the format required for the Master's Theorem; thus, it can be rewritten simply by considering the highest power term as θ(n²).

Step-by-step explanation:

Finding Upper and Lower Bounds for θ(n⁷)

To find the upper bound and lower bound constants for the function T(n) = 5n⁷ + n + 2n², we compare the given function to cn⁷ to demonstrate that it is θ(n⁷). We look for constants c1 and c2 such that c1n⁷ ≤ T(n) ≤ c2n⁷ for all n ≥ n0. By taking the highest degree term, we can disregard the lower degree terms for large values of n. Thus, we can find such constants c1 and c2 that satisfy the inequality for large n.

To rewrite the function T(n) = 10n² + 5n + 1 + 3 · T(⅔n) in the form T(n) = θ(n²) + a · T(⅔n), we consider the first part, 10n² + 5n + 1, as our θ-term. Since n² is the highest power and dominates the growth of the function, our θ-term would be θ(n²). The function then can be rewritten as T(n) = θ(n²) + 3 · T(⅔n), which is in the required Master's Theorem form.