Problem 3. Consider the following recurrence, defined for n a power of 4 (for the time of some algorithm): T(n) = 3 if n = 1 2T(
n/4) + 4n + 1 otherwise (a) Calculate T(16) by hand. Show your work. (b) Use the tree method to solve the recurrence exactly, assuming n is a power of 4. (c) Use the formula to calculate T(1). Show your work. (d) Use the formula to calculate T(4). Show your work. (e) Use the formula to calculate T(16). Show your work. (f) Use Mathematical Induction to prove that your formula is correct in general.
1 answer:
You might be interested in
Answer:
Code is provided in the attachment form
Explanation:
Vector Multiplication code:
Vector_multiplication.c file contains C code.
See attachment no 1 attached below
Classification of Algorithm: For creating elements in vector c of size n, number of scalar multiplications is equal to n. The size of original two vectors scales directly with the number of operations. Hence, it is classified as O(n).
