Another time complexity issue [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

I've done these problems, so I am not looking for a straight answer. I am looking for guidance on whether or not I am doing this correctly and if not, possibly some explanation on why I am incorrect. :)

So I have these two problems. I've commented my logic in why I got to my answers. If someone could please verify that I am doing this correctly?

public static Integer findTripleB(int[] anArray) {
//Method Variable: n
       if (anArray.length <= 2) {
          return false;
       }                //Time Complexity: 1
       // use insertion sort to sort anArray
       for (int i = 1; i < anArray.length; i++) {//TC 1+(n+1)+n
          // insert anArray[i]
          int j = i-1; //TC 1
          int element=anArray[i]; //TC 1
          while (j >= 0 && anArray[j] > element) {//TC log(n)
             anArray[j+1] = anArray[j]; //TC 1
             j--; //TC 1
          }
          anArray[j+1] = element; //TC 1
       } //Total TC: (2n+2)(1+1+log(n)(2)) = (2n+2)(2+2log(n)) = 4n+(2log(n))(2n)+4+4log(n)
       // check whether anArray contains three consecutive 
       // elements of the same value
       for (int i = 0; i < anArray.length-2; i++) {//TC 1+n-1+n
          if (anArray[i] == anArray[i+2]) {//TC 1
             return new Integer(anArray[i]);//TC 1
          }
       }//Total TC: (2n)(2) = 4n
       return null;//TC 1
        }   //TOTAL TIME COMPLEXITY: 5+8n+4nlog(n)+4log(n)

For best case time complexity, I got O(1) because if the array is >= length 2, it would return. For worst case, I came up with O(n*log(n)).

For one more simpler problem,

boolean findTripleA(int[] anArray) { //Method Variable: n
   if (anArray.length <= 2) {
      return false;//TC 1
   }//TC 1
   for (int i=0; i < anArray.length; i++) {//TC 1+n+1+n
      // check if anArray[i] occurs at least three times 
      // by counting how often it occurs in anArray
      int count = 0;//TC 1
      for (int j = 0; j < anArray.length; j++) {//TC 1+n+1+n
         if (anArray[i] == anArray[j]) {
            count++;
         }//TC 1
      }//Total TC: 2n+2
      if (count >= 3) {
         return true;
      }//TC 1
   }//Total TC: (2n+2)(1+2n+2+1) = (2n+2)(2n+4) = 4n2+12n+8
   return false;//TC 1
}//TOTAL TIME COMPLEXITY: 4n2+12n+9

For best case, same as the first problem, O(1). For worst case, O(n^2).

Are these correct and, if not, why not? Again, I'm not looking for an answer. I'm looking for guidance as my professor doesn't seem to want to help and the rest of the class is just as confused.

Answer 1

A few points here for the first example:

Complexity analysis of algorithms is not about a single case of the algorithm (with an array size of 2 for example), but rather about how long the algorithm will take in the best/worst/average case for arbitrarily-sized inputs (so an array of any given size). Technically, you do the analysis looking at the behavior as n (the size of the input) tends to infinity. Therefore, the if statements before your loops do not affect the asymptotic best-case performance of the algorithms.

Insertion sort's worst case is O(n^2). You can get this kind of time if the input array is already sorted but in reverse order. So your conclusion for the first case is wrong. So that I don't have to write a lengthy description of why this is the case, here's an explanation for why it's O(n^2) from here:

It's not entirely clear, however, how much longer the inner while loop will take if we have twice the array size. After all, it doesn't go through the entire array. In fact, on average, it only goes through about half the array, as our diagram here illustrates, sometimes less, early in the sort, and sometimes more, later in the sort, but half of the array on average. And even then it doesn't usually go all the way down to index 0. It will, again on average, scan through about half the sorted set before finding the right spot. So, it's reasonable to estimate that the inner-while loop must iterate through ¼ of the array for each time through the outer for-loop. The sorted set it must search averages half the size of the array, and on average it must hunt through half the sorted set before finding the right spot.

But, even if it's just ¼ of the array, that will still double if the array size doubles -- ¼ of 1000 is 250, and ¼ of 2000 is 500, twice as much. And so when the array size doubles, the inner while loop takes twice as long on average, and it must be performed twice as many times by the outer for loop. Thus insertion sort takes 4 times as long to run when the array size doubles. It's run time is proportional to n^2, and we say it is O(n^2).

For the best-case, you are wrong too. Even if it "just returns" you are still going to go through a number of comparisons proportional (really, equal) to the number of elements in the array (even if it's just 2 elements). So the best-case is O(n) comparisons, as you will have to check whether each element is in its right position, but O(1) swaps (in case it's already sorted in the right order and there's nothing to swap anywhere).

Also, in your code, you are returning a boolean in one place and Integers in two other places of the same method. This doesn't make sense.

Hopefully that's all clear.

Answer 2

Generally, trying to go much beyond order of magnitude isn't meaningful. If there's an N-squared term, you can call it O(N**2) and leave it at that. If you want more accuracy, I'd suggest running a profiler on it... with the caveat that hotspot optimization and JIT nondeterminacy and GC time all conspire to make fine measurements of performance difficult in Java.