procedure mystery(int n, int a) if (n == 0) then return 0 end if int tmp1 = MYST
ID: 3562859 • Letter: P
Question
procedure mystery(int n, int a)
if (n == 0) then
return 0
end if
int tmp1 = MYSTERY(n/2, a) //assume n/2 rounds down.
int tmp2 = 0
for int i = 1 to n/2 do
tmp2 + = a
end for
if (n%2 == 1) then
return tmp1 + tmp2 + a
else
return tmp1 + tmp2
end if
end procedure
------------------------------------
1. Consider the previous recursive algorithm MYSTERY that takes as input integers
n and a
(a) What does the mystery function compute?
(b) Set up a runtime recurrence for the mystery method above. Do not forget the
base case.
(c) Is this mystery function a divide-and-conquer algorithm? Briefly justify your
answer.
------------------------------
3. Consider the following runtime recurrence: T(1) = 1 and T(n) = 3T(n/2) + n2
when n 2. Use big-Oh induction to prove that T(n) 2 O(n2).
Explanation / Answer
1)
a)
The mystery function computes the sum two cubes.
b)
public class Algorithm
{
public int mystery(int n, int a)
{
if (n == 0)
{
return 0;
}
//assume n/2 rounds down.
int tmp1 = mystery(n/2, a);
int tmp2 = 0;
for (int i = 1;i<n/2;i++)
{
tmp2 += a;
}
if (n%2 == 1)
{
return tmp1 + tmp2 + a;
}
else
{
return tmp1 + tmp2;
}
}
public static void main(String args[])
{
Algorithm a=new Algorithm();
int x=a.mystery(20,2);
System.out.println("The mystery value is : "+x);
}
}
Sample output is:
The mystery value is : 32
c)
Yes, the function is using divide and conquer method. Because at the statement,
int tmp1=mystery(n/2, a); it is dividing the value of n and to get the value for tmp1.
By recursive function, it is able to combine all the values of tmp1.
------------------------------------------------------------------------------------------------------------------------
3)
Provided T(1)=1.
T(n) = 2* T(n/2) + n2 when n=2; ……(1)
According to Master’s theorem, if f(n)=O(nc) where c< logba then:
……(2)
For T(n)=aT(n/2) + f(n); where a>1 and b>2. ……(3)
When equation (3) is compared with equation (1), then a and b values obtained are:
a=2 and b=2.
Now, substitute the values in equation (2) then,
T(n) = ? (nlog22)
= ? (n1)
= ? (n)
T(n)= ? (n) + O(n2) where the value of n2 is always greater.
The function T(n) =c O(n2). Here c=2.
Therefore, T(n) =2 O(n2).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.