A. What is the growth function of the following methods? Method 1: public int my
ID: 3601865 • Letter: A
Question
A. What is the growth function of the following methods?
Method 1:
public int mystery1(int n )
{
int sum = 0;
for(int i = 0; i < n ; i++)
{
for(int j = 0; j < i; j++)
{
sum += i * j;
}
}
return sum;
}
Method 2:
public int mystery2(int n )
{
int sum = 0;
for(int i = 0; i < 10 ; i++)
{
for(int j = 0; j < i; j++)
{
sum += j * n;
}
}
return sum;
}
B. What is the order(Big-Oh or computational complexity) of the following methods?
Method 1:
public int mystery1(int n )
{
int sum = 0;
for(int i = 0; i < n ; i++)
{
for(int j = 0; j < i; j++)
{
sum += i * j;
}
}
return sum;
}
Method 2:
public int mystery2(int n )
{
int sum = 0;
for(int i = 0; i < 10 ; i++)
{
for(int j = 0; j < i; j++)
{
sum += j * n;
}
}
return sum;
}
C. Write a Java statement that instantiate an array of 1001 generic objects (You may use the common E for the generic data type).
Explanation / Answer
A.
Method 1
i is not being modified anywhere inside the inner loop.
When i=0, the inner loop runs for 0 times.
When i=1, the inner loop runs for 1 times
When i=2, the inner loop runs for 2 times
When i=n-1, the inner loop runs for n-1 times.
Adding these together, 1+2+….n-1= n*(n-1)/2
Thus the growth function of the method is n*(n-1)/2
Method 2
i is not being modified inside the inner loop
When i=0, the inner loop runs for 0 times.
When i=1, the inner loop runs for 1 times
When i=2, the inner loop runs for 2 times
When i=9(say n), the inner loop runs for 9(say n) times.
Adding these together, 1+2+….9= 9*(10)/2=45 times
[ 1+2+3+…n= n(n+1)/2]
Thus the growth function of the method is n*(n+1)/2 if i iterates from 0 to (n+1) in the outer loop.
B
Method 1
From part A, Method 1 , the growth function is n*(n-1)/2.
Since the growth function is a polynomial of degree 2, we can just take the highest factor in the polynomial and say that the computational complexity is O(n2).
Method 2
From part A, Method 2 , the growth function is n*(n+1)/2.
Since the growth function is a polynomial of degree 2, we can just take the highest factor in the polynomial and say that the computational complexity is O(n2).
C. E[] arr= (E[])new Object[1001];
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.