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.