I need help determining the worst case running times for these methods and denot

Question

 I need help determining the worst case running times for these methods and denoting the big-O notation. I'm just not sure how to start analyzing them.  public void add(int element) {       if (manyItems == data.length)       {           int biggerArray[ ];                      biggerArray = new int[manyItems*2 + 1];           for(int i=0;i < manyItems;i++){                biggerArray [i] = data[i];           }           data = biggerArray;       }        data[manyItems] = element;       manyItems++; } 

 public int countOccurrences(int target) {       int answer = 0 ;       int index;              answer = 0;       for (index = 0; index < manyItems; index++)          if (target == data[index])             answer++;       return answer; } 

 public static IntNode listPosition(IntNode head, int position) {   IntNode cursor;   int i;               if (position <= 0)        throw new IllegalArgumentException("position is not positive");               cursor = head;   for (i = 1; (i < position) && (cursor != null); i++)      cursor = cursor.link;            return cursor; } 

 public static int listLength(IntNode head) {            IntNode cursor = null;            int answer = 0;                        for (cursor = head; cursor != null; cursor = cursor.link)               answer++;                          return answer; } 

Explanation / Answer

Big O notation analyzes code to see how it will run under very large data set circumstances and worst possible case. You then average the best case and worst case occurances to get the order

public void add(int element) //This function is O(1) because the worst case scenario only happens every n times (O(n)/n) = 1

{

      if (manyItems == data.length) //Data length here is the value we are interested in analyzing

      {

          int biggerArray[ ]; //O(1) order 1 times (runs once no matter what)

          biggerArray = new int[manyItems*2 + 1]; //O(1) order 1 times (runs once no matter what)

          for(int i=0;i < manyItems;i++){ //Right here the code will run O(n) (order n times) if the it has to resize the array

               biggerArray [i] = data[i];     //O(n)

          }

          data = biggerArray; O(1)

      }

      data[manyItems] = element; //O(1)

      manyItems++; //O(1)

}

public int countOccurrences(int target) //this function is O(n)

{

      int answer = 0 ; //O(1)

      int index; //O(1)

      answer = 0; //O(1)

      for (index = 0; index < manyItems; index++) //O(n) will run this n times every time

         if (target == data[index]) //O(n)

            answer++; //O(n)

      return answer; //O(1)

}

public static IntNode listPosition(IntNode head, int position) //This function is O(n)

{

IntNode cursor; //O(1)

int i; //O(1)

if (position <= 0) //O(1)

       throw new IllegalArgumentException("position is not positive");

cursor = head; //O(1)

for (i = 1; (i < position) && (cursor != null); i++) //O(n) has a possibility of being in position n (n very large)

     cursor = cursor.link; //O(n)

return cursor; //O(1)

}

public static int listLength(IntNode head) //This function is O(n)

{

           IntNode cursor = null; //O(1)

           int answer = 0; //O(1)

           for (cursor = head; cursor != null; cursor = cursor.link) //O(n) cursor could be in the last position

              answer++; //O(n)

           return answer; //O(1)

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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