Question

1. What is the Big-O run-time of linear search and binary search in the best, average and worst cases?

      Linear Search                  Binary Search

Best:

Worst:

Average:

2. What is the Big-O runtime of the following linked list methods?

• addFirst()
• toString()

What is the Big-O runtime of the below Stack method?

• isSorted(Node n)

3. What is the Big-O runtime of the below methods:

Method A: Stack Copy Constructor Option 1

public Stack(Stack<T> original) { 
    if(original == null) {
       return;
    } else if (original.length == 0) {
       this();
    } else {
       Node current = original.top;
       Stack<T> temp = new Stack<>();
       while (current != null) {
          temp.push(current.data);
          current = current.next;
       }       current = temp.top;
       while (temp != null) {
           this.push(current.data);
           current = current.next;
       }
       this.length = original.length;
    }
}

Method B: Stack Copy Constructor Option 2
public Stack(Stack<T> original) {
   if (original.length == 0) {
      top = null;
      length = 0;
   } else {
      top = new Node(original.top.data);
      Node temp1 = original.top;
      Node temp2 = top;
      for (int i = 0; i < original.getLength() - 1; i++) {
         temp1 = temp1.next;
         temp2.next = new Node(temp1.data);
         temp2 = temp2.next;
      }
      length = original.length;
   }
}
Method C: Stack Copy Constructor Option 3:

public Stack(Stack<T> original) {
   if (original == null) {
       return;
   } else if (original.length == 0) {
      this.length = 0;
      this.top = null;
   } else { 
      int count = original.getLength();
      while (count > 0) {
         count--;
         Node temp = original.top;
         int i = 0;
         while (temp.next != null && i < count) {
            i++;
            temp = temp.next;
         } //end inner while
         push(temp.data);
      } //end outer while
   } //end else
}//end method

Answer 1

Q.No.1:-

Linear Search:-                 

Best: O(1)               {element to be searched is the first element of the list }               

Average: O(n/2) = O(n) {element is present at the middle of the list}

Worst: O(n)    {element to be searched is the last element of the list or the element is not present in the list }      

Binary Search:-{ it cuts down the search to half at every iteration, but given array must be sorted}

Best: O(1)          {element to be searched is the middle most element, searches an element in constant time }                           

Average: O(logn) {search starts at middle}

Worst: O(logn){wost case that is the maximum number of comparisons to search element }

Q.No.2:- (a) addFirst() has O(1) compelxity..infact every 'insert' operation whether it is at begining or at any position of the linked list complexity is O(1) complexity....

(b) O(n^2) in worst case as two while loops are to be used in tostring()...

METHOD A:- O(n) as not nested while

METHO B:- O(n) where n is the length inputted

METHOD C:-O(n^2) as two while loops are to be used...

kindly comment if you need further elaboration ..please give like if you find it needfull..