Please Do Question 1 below This question refers to the imple

Please Do Question 1 below:

This question refers to the implementation of a bigInteger from Assignment #1. I added three methods to the LinkedList class so that bigInteger values can be compared (given below). Let x be a bigInteger value with n digits and let y be a bigInteger with n + k digits for some k 0. The compare method is called like this: int cmp= x.compare(y);

1(a) [2] Give an example of two big integers (leading zeroes are allowed) that represent a worst case example for the running time of the compare method when n = 8 and k = 7.

1(b) [3] Give a description of a family of worst case examples (expressed in terms of n and k) such that on your examples, the number of calls to compareDigit is maximized.

1(c) [4] How much time (in terms of n and k) does the nonZeroDigit method take on your worst case examples? Justify your answer.

1(d) [4] Derive a recurrence T(n) which represents the time complexity of the compareDigit method on your worst case example. Explain where each part of the recurrence is coming from.

1(e) [4] Solve your recurrence from part (d) by repeated substitution, numbering the steps starting at Step 0.

1(f) [4] Prove that you have the correct solution to the recurrence by induction.

1(g) [4] How much time does the compare method take in the worst case (in terms of n and k)? Justify your answer. Keep in mind that if k is large, for example k = n 5 then the dominant term could depend on k and when k is small, for example, k = 0, the dominant term could depend on n. As a result, it is critical that your answer is a function of both n and k.

Code Needed to solve question 1:

/* This method returns: -1 if the bigInteger associated with the method is less than y 0 if the bigInteger associated with the method is equal to y +1 if the bigInteger associated with the method is greater than y */

public int compare(LinkedList y) {

int nv;

// If one has more digits than the other, check if any

// of the extra digits are non-zero- if so, the one with

// more digits is bigger.

//Block 1

nv= n;

if (n > y.n) {

if (nonZeroDigit(y.n))

return(1); nv= y.n; }

else if (y.n > n) {

if (y.nonZeroDigit(n))

return(-1); }

// Block 2

// Compare digits starting with most significant ones.

return(compareDigit(nv, y)); }

public boolean nonZeroDigit(int nIgnore) {

ListNode current;

int i;

current= start;

for (i=0; i < nIgnore; i++)

current= current.next;

while (current != null) {

if (current.data != 0)

return(true);

current= current.next; }

return(false); }

public int compareDigit(int nv, LinkedList y) {

int dx, dy;

ListNode xcurrent, ycurrent;

int i; if (nv ==0) return(0); // They are equal.

// Get xcurrent/ycurrent to point to cell nv of x/y.

xcurrent= start;

ycurrent= y.start;

for (i= 1; i < nv; i++) {

xcurrent= xcurrent.next;

ycurrent= ycurrent.next; }

dx= xcurrent.data;

dy= ycurrent.data;

if (dx < dy) return(-1);

if (dx > dy) return( 1);

return(compareDigit(nv-1, y)); }