Question: 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
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?
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help