Question

What is the runtime of each method? Give answer in Θ(big Theta) notation as a function of n, give a brief explanation.

A. public static int method1(int n){

int mid = n/2;

for (int i = mid; i >= 0; i--) System.out.println(i);

for (int i = mid + 1; i <= n; i++) System.out.println(i);

return mid;

}

B. public static int method2(int n){

for (int i = n; i >= 0; i / 3){

System.out.println(i );

}

return mid;

}

C.public static int method3(int n){

for (int i = n; i >= 0; i--){

for (int j = 0, j <= i + i; j++)

System.out.println(i + j);

}

return mid;

}

D. public static int method4(int [] a, int start, int end){

int ans = 0;

if (start >= end) ans = a[start];

else {

int mid = (start + end) / 2;

int x = method4(a, start, mid);

int y = method4(a, mid + 1, end);

print(a, start, end); //print each element in a from start to end

if (x < y) ans = x;

else ans = y;

}

return ans;

}

public static void print(int [] a, int s, int e){

for (int i = s; i <= e; i++) System.out.println(i);

}

Answer 1

A. answer)

public static int method1(int n){

int mid = n/2;

for (int i = mid; i >= 0; i--)

System.out.println(i);

for (int i = mid + 1; i <= n; i++)

System.out.println(i);

return mid;

}

Here  for (int i = mid; i >= 0; i--) System.out.println(i); loop runs n/2 times.

and for (int i = mid + 1; i <= n; i++) System.out.println(i); loop runs n/2+1 times.

Total time is (n/2 ) + (n/2+1)=Big Theta(n)

B)answer)

public static int method2(int n){

for (int i = n; i >= 0; i / 3){

System.out.println(i );

}

return mid;

}

here for (int i = n; i >= 0; i / 3){ System.out.println(i ); runs log₃ n times

Total time is Big Theta(log₃ n)

c)answer)

public static int method3(int n){

for (int i = n; i >= 0; i--){

for (int j = 0, j <= i + i; j++)

System.out.println(i + j);

}

return mid;

}

for i=n , j loop runs 2n times

for i=n-1 ,j loop runs 2n-2 times..

for i=n-2 ,j loop runs 2(n-2) times.

'

'

for i=1 ,j loop runs 2 times.

total 2+2*2+2*3+------+2(n-1)+2n

=bigtheta(2(n^2))=bigtheta(n^2)

D.answer)

public static int method4(int [] a, int start, int end){---->assume This as T(n)

int ans = 0;

if (start >= end) ans = a[start];

else {

int mid = (start + end) / 2;

int x = method4(a, start, mid); --------------->Tn/2)

int y = method4(a, mid + 1, end);-------------->T(n/2)

print(a, start, end); //print each element in a from start to end

if (x < y) ans = x;

else ans = y;

}

return ans;

}

public static void print(int [] a, int s, int e){

for (int i = s; i <= e; i++) System.out.println(i);

}

here

public static void print(int [] a, int s, int e){

for (int i = s; i <= e; i++) System.out.println(i);

} runs bigtheta(e-s)time

T(n)=2T(n/2)+c

apply masters therom T(n)=bigtheta(n^log_bb)=bigtheta(n)

total time is log(e-s)+n=bigtheta(n)