Question

1. Use the substitution method to show that the recurrence T(n) = √ n T( √ n) + n has a solution T(n) = O(n lg lg n).

2. Determine the Theta-Bounds of the following functions by using the method of your choice:
I. f(n) = n + n² + 2n + n⁴
II. f(n) = (log n)² + 2n
A) 1. True, 2. O(n⁴), Θ(n⁴)
B) 1. True, 2. O(n⁴), Θ(n²)
C) 1. False, 2. O(n⁴), Θ(n²)
D) 1. False, 2. O(n⁴), Θ(n⁴)

Answer 1

To use the substitution method to show that the recurrence T(n) = √ n T( √ n) + n has a solution T(n) = O(n lg lg n), you can assume that T(n) ≤ cn lg lg n and substitute it into the recurrence relation. To determine the Theta-Bounds of the functions f(n) = n + n² + 2n + n⁴ and f(n) = (log n)² + 2n, analyze the dominant terms in these expressions.

Step-by-step explanation:

To use the substitution method to show that the recurrence T(n) = √ n T( √ n) + n has a solution T(n) = O(n lg lg n), we can make the assumption that T(n) ≤ cn lg lg n for some constant c. Substituting this assumption into the recurrence relation, we get T(n) ≤ √ n (c√ n lg lg (√ n) + √ n). Simplifying further, we get T(n) ≤ c √ n lg lg n + n. Since n lg lg n is O(n), we can conclude that T(n) is also O(n lg lg n).

To determine the Theta-Bounds of the functions f(n) = n + n² + 2n + n⁴ and f(n) = (log n)² + 2n, we need to analyze the dominant terms in these expressions. For the first function, the dominant term is n⁴. Hence, f(n) = Θ(n⁴). For the second function, the dominant term is (log n)². Therefore, f(n) = Θ((log n)²).