Clever Geek Handbook

Which Big-O record falls into this category?

Which Big-O notation falls under this? I know that setSearch () and removeAt () are of order O (n) (let's assume they are anyway). I know that without a for loop it would be O (n) for sure, but I am confused how to figure out what it does with a for loop thrown into it. I'm not that good at math ... right. Will it be O (n ^ 2)?

public void removeAll(DataElement clearElement)
{
     if(length == 0)
         System.err.println("Cannot delete from an empty list.");
     else
     {
         for(int i = 0; i < list.length; i++)
         {      
            loc = seqSearch(clearElement);

            if(loc != -1)
            {      
               removeAt(loc);
                --i;
             }
         } 
     } 
}
+3


source to share


1 answer


If removeAt () and seqSearch () are O (n) relative to the length of the list, then yes, this algorithm will be O (n ^ 2). This is because in the for loop you call seqSearch every time, with the option to call removeAt (loc). This means that for each iteration, you do either n or 2n operations. In the worst case, you have 2n ^ 2 operations, which is O (n ^ 2).



+2


source






More articles:


All Articles