Suppose you have a singly-linked list of Node objects with double data elements.

Question

Suppose you have a singly-linked list of Node objects with double data elements. The Node

class is provided below.

class Node {

double data;

Node next;

}

Consider that head is the reference variable that holds the starting node of the linked list you have.

Obviously, head is an instance of the Node class.

(a) Write a recursive method named countBelowThreshold that counts the number of items in the

linked list whose data value is smaller than a provided threshold.

public int countBelowThreshold(Node head, double threshold) {

}

(b). What is the time complexity (big-oh) of the countBelowThreshold method you have written?

Explanation / Answer

(a)

public int countBelowThreshold(Node head, double threshold) {
   if(head==null)
       return 0;
  
   if(head.data<threshold){
       return 1+ countBelowThreshold(head.next,threshold);
   }
   else
   {
       return 0+countBelowThreshold(head.next,threshold);
   }
}

b) complexity of the code is O(n) since we are traversing whole linkedlist

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.