in at least 300 words describe the algorithm used below and it\'s complexity . R
ID: 3768721 • Letter: I
Question
in at least 300 words describe the algorithm used below and it's complexity. Restrain from describing what the code does unless it support the description of the algorithm or complexity.
public int Largest(Node node, int sum, int subsetSize){
if(node == null){
return sum == 0 ? subsetSize : 0;
}
int subsetSizeWith = Largest(node.next, sum + node.item, subsetSize++);
int subsetSizeWithout = Largest(node.next, sum, subsetSize);
return subsetWith > subsetWithout ? subsetWith : subsetWithout;
}
Explanation / Answer
the algorithm here returns the length of the node network.
N1->N2->null
the algorithm would return 2. in this case.
The complexity is O(n^2) [it scans the complete list in recursive manners twice one for subsetSizeWith and subsetSizeWithout ]
Sample code to see this code working :
============ Node.java===
public class Node {
Node next;
int item;
}
====
=====NodeTest.java=========
public class NodeTest {
public static void main(String[] args) {
Node n13 = new Node();
n13.item=20;
n13.next=null;
Node n12 = new Node();
n12.item=15;
n12.next=n13;
System.out.println("largest "+Largest(n12,0,0));
}
public static int Largest(Node node, int sum, int subsetSize){
if(node == null){
System.out.println("sum "+sum);
System.out.println("subsetSize "+subsetSize);
return sum == 0 ? subsetSize : 0;
}
int subsetSizeWith = Largest(node.next, sum + node.item, subsetSize++);
System.out.println("subsetSizeWith"+subsetSizeWith);
int subsetSizeWithout = Largest(node.next, sum, subsetSize);
System.out.println("subsetSizeWithout"+subsetSizeWithout);
return subsetSizeWith > subsetSizeWithout ? subsetSizeWith : subsetSizeWithout;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.