1.) The sub method in the following block of code implements subtraction of natural numbers using the linked-list formulation we covered in class. What is the complexity of the division operation in big-O notation? Justify your answer.

public class Nat {

 static class Inner {

 Inner(Inner n) {

 next = n;

 }

 Inner next;

 }

 Inner inner;

 public Nat sub(Nat other) {

 Nat nat = new Nat();

 nat.inner = this.inner;

 Inner p = other.inner;

 while (p != null && nat.inner != null) {

 nat.inner = nat.inner.next;

 p = p.next;

 }

 return nat;

 }

}

--------------------------------

2.) The pow method in the following block of code implements exponentiation of natural numbers using the linked-list formulation we covered in class. What is the complexity of the division operation in big-O notation? Justify your answer.

public class Nat {

 static class Inner {

 Inner(Inner n) {

 next = n;

 }

 Inner next;

 }

 Inner inner;

 public Nat add(Nat other) {

 Nat nat = new Nat();

 nat.inner = this.inner;

 Inner p = other.inner;

 while (p != null) {

 nat.inner = new Inner(nat.inner);

 p = p.next;

 }

 return nat;

 }

 public Nat mul(Nat other) {

 Nat nat = new Nat();

 Inner p = other.inner;

 while (p != null) {

 nat = nat.add(this);

 p = p.next;

 }

 return nat;

 }

 public Nat pow(Nat other) {

 Nat nat = new Nat();

 nat.inner = new Inner(null);

 Inner p = other.inner;

 while (p != null) {

 nat = nat.mul(this);

 p = p.next;

 }

 return nat;

 }

}

--------------------------

3.) Why might you prefer to use a linear search instead of a binary search on a short (say <10 elements), sorted array?