1) int multiply(int a, int b){ if (a == 0){ return 0; }else { return b + multipl
ID: 3622354 • Letter: 1
Question
1) int multiply(int a, int b){if (a == 0){
return 0;
}else
{
return b + multiply(a-1, b);
}
}
2) void printScientificNotation(double value, int powerOfTen){
if (value >= 1.0 && value < 10.0){
System.out.println(value + " x 10^" + powerOfTen);
}
else if (value < 1.0){
printScientificNotation(value * 10, powerOfTen - 1);
}
else // value >= 10.0{
printScientificNotation(value / 10, powerOfTen + 1);
}
}
3)IntNode delete(IntNode head, int target){
if (head == null){
return null;
}
else if (head.data == target){
return head.next;
}
else
{
head.next = delete(head.next, target);
return head;
}
}
4)IntNode interleave(IntNode head1, IntNode head2){
if (head1 == null){
return head2;
}
else{
head1.next = interleave(head2, head1.next);
return head1;
}
}
5)int differenceInLengths(IntNode head1, IntNode head2){
if (head1 == null && head2 == null)
{
return 0;
}
else if (head1 == null && head2 != null){
return 1 + differenceInLengths(null, head2.next);
}
else if (head1 != null && head2 == null){
return 1 + differenceInLengths(head1.next, null);
}
else{
return differenceInLengths(head1.next, head2.next);
}
}
Explanation / Answer
We assume that the running time of basic operator is O(1) (constant time) Let T(n) is the running time of each algorithm. 1) T(n)=1 if a==0, T(n)=a if a!=0 (I think a must >0) 2) T(n)=1 if value >= 1.0 && value < 10.0 T(n)=lg(value) otherwise (lg mean log 10) 3)In the worst case, we must search though all node in the list, so the running time is O(n). Where n is number of node in the list. 4) T(n)=k where k is number of internode between head1 and leaf 5)T(n)=Max(l1,l2). Where l1 is the length of head1 (number of node in head1), and l2 is length of head2.Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.