Give the worst-case time complexity for your method below expressed in \"Big-O\"

Question

Give the worst-case time complexity for your method below expressed in "Big-O" notation. Include a brief justification for the time complexity you give and include any assumptions you make about the complexity of methods that are called by your implementations.

Also, why can i not copy paste this code and run it?

public static int removeAll(String target, DoubleListnode<String> chain)
{
   if ( null == target ) throw new IllegalArgumentException();

//confirming header node not required
if ( null == chain ) throw new IllegalArgumentException();

int count = 0; //count of removed nodes

//note: curr points to existing node
DoubleListnode<String> curr = chain; //start at the header node

   //If there is only a single node present in the list  
   if(curr.getPrev() == NULL && curr.getNext() == NULL)
   {
       //If node is the target node
       if(curr.getData().equals(target))
       {
           curr = NULL;
       }
   }
   else
   {
       //Moving till last but one node
       while(curr.getNext()!= null)
       {
           if(curr.getData().equals(target))
           {
               //If the node is a head node
               if(curr.getPrev() == NULL)
               {
                   curr.getNext().setPrev() = NULL;
               }
               else //Node is not a head node
               {
                   curr.getNext().setPrev() = curr.getPrev();
                   curr.getPrev().setNext() = curr.getNext();
               }
               count++;
}
           else
           {
               //move curr to the next node
               curr = curr.getNext();
           }
       }
      
       //If last node is target node
       if(curr.getData().equals(target))
       {
           curr.getPrev().setNext() = NULL;
           count++;
       }
   }
return count;
}

Explanation / Answer

Big O notation describes the limiting behavior of a function.
The worst-case time complexity means for user input the program will
need worst rather than normal.
The function describes that takes double Linked list and target atring.
if target string is equals with data in list then remove and count
number of target elements(data) is there in list remove and return the count.

The Worst-case Time complexity of the function is O(N)

we know that constant statemnts means single line statement not executed
more than one is need 1 unit time like in notation O(1)

if statement also constant time is O(1)

in function only one while loop runs n-1 times where n is elements in
list thats not fixed.
in while have multiple if statements,and single statements
all have executed n-1 times. so that for while time complexity isO(n)

from all constatnt statements are negligible so that

worst case time complexity is O(N)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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