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:
Following are the program to this question:
import java.util.*; //import package
public class Main //defining class
{
public static void main(String[] args) //defining main method
{
int testedEmployee; //defining integer variable
for(int i = 1;i<=52;i++) //defining loop that counts from 1 to 52
{
testedEmployee = 1 + (int) (Math.random() * 30); //using random method that calculate and hold value
System.out.print(testedEmployee+"\t"); //print value
if(i%4 == 0)//defining codition thats checks value is divisiable by 4
{
System.out.println(); //print space
}
}
}
}
Output:
please find the attachment.
Explanation:
In the given java program, a class Main is declared, inside the class, the main method is declared, in which an integer variable "testedEmployee", is declared, in the next line, the loop is declared, that can be described as follows:
- Inside the loop, a variable "i" is declared, which starts from 1 and stop when its value is 52, inside the loop a random method is used, that calculates the random number and prints its value.
- In the next step, a condition is defined, that check value is divisible 4 if this condition is true, it will print a single space.
