A. Construct a RECURSIVE solution for following iterative solution to find a value in a circular-linked list B. Analyze the runtime complexity (correctly explain the scenario, show how much work would be done, and represent the work using asymptotic notations, i.e. big O), of the given iterative solution and your recursive solution for the best case scenario and the worse case scenario. C. prove the correctness of your recursive solution by induction /** @param value - a value to search for @return true if the value is in the list and set the current reference to it otherwise return false and not updating the current reference */ public boolean find(T value){ if(this.cur == null) return false; //get out, nothing is in here Node tmp = this.cur; //start at the current position if(tmp.data == value) return true; // found it at the starting location tmp = tmp.next; //adv. to next node, if there is one while(tmp != cur) { if(tmp.data == value){ this.cur = tmp; //update the cur reference to the found node return true; } tmp = tmp.next } return false; //not found }
A. Construct a RECURSIVE solution for following iterative solution to find a value in a circular-linked list
B. Analyze the runtime complexity (correctly explain the scenario, show how much work would be done, and represent the work using asymptotic notations, i.e. big O), of the given iterative solution and your recursive solution for the best case scenario and the worse case scenario.
C. prove the correctness of your recursive solution by induction
/**
@param value - a value to search for
@return true if the value is in the list and set the current reference to it
otherwise return false and not updating the current reference
*/
public boolean find(T value){
if(this.cur == null)
return false; //get out, nothing is in here
Node<T> tmp = this.cur; //start at the current position
if(tmp.data == value)
return true; // found it at the starting location
tmp = tmp.next; //adv. to next node, if there is one
while(tmp != cur) {
if(tmp.data == value){
this.cur = tmp; //update the cur reference to the found node
return true;
}
tmp = tmp.next
}
return false; //not found
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
