Skip to content
Advertisement

Analysis of run time complexity

I need some help below I have some code I created for an assignment. I am having a hard time figuring out the time complexity of this algorithm. I looked at it and believe the O-notation is 0(n) and the function is F(n)= 4 + 2n. But I think that is incorrect.

/**
*mostOften method 
*@param receives Array[] , int
*/

 static int mostOften(int array[] , int n){
 
 //Array to be sorted in ascending order
 Arrays.sort(array);
 
 //counts number of max occurrences in the array
 int maxO = 1;
 
 //Keeps track of the integer at Array[i].
 int result = array[0];
 
 //variable to count occurrences
 int count = 1;
 
 /**
 *loop passes through array in linear motion and compares index at i and index at
 * i - 1. For every possible outcome count and maxO are incremented accordingly.
 */
  for(int i = 1 ; i < n ; i++){ 
  
        //If integers are the same increment count.
            if (array[i] == array[i - 1]){ 
                count++;  
            }//close if statement
            
        // else if integers are not the same 
         else{
         
               //if count is larger thatn maxO that integer is the highers occurrence
                if (count > maxO){ 
            
                   //count is now maxO
                    maxO = count; 
               
               //replaces result with integers with highest occurrence.
                    result = array[i - 1]; 
                }//close if statement
             
            //reset count to 1.
                count = 1; 
            
            }//close else statement
         
  }//close for loop
  
      //@returns int data type
        return result;
  
 }//close mostOften method

Advertisement

Answer

Just wanted to point out that Arrays.sort itself is O(n logn). If we ignore that, the loop takes linear time.

User contributions licensed under: CC BY-SA
9 People found this is helpful
Advertisement