Can anyone provide a basic example of O-notation in Java?

Question

i am trying to find limitations of o notations, i was wondering if there was a simple example that demonstrates an enahncement to a task, where version 1 is the same o notation as version 2, yet version 2 works more efficiently after the enhancement

thanks

Answer 1

In the following code, the addition of a line after the // do something to break out of the inner loop leaves a faster function, but still one that is O(n^2).

for (int i = 0; i < n; i++) {
   for (int j = 0; i < n; j++) {
        if (i == j) {
            // do something
        }
   }
}

Answer 2

This Merge-sort code work in nLog(n):

/**
 * Mergesort algorithm.
 * @param a an array of Comparable items.
 */
public static void mergeSort( Comparable [ ] a ) {
    Comparable [ ] tmpArray = new Comparable[ a.length ];
    mergeSort( a, tmpArray, 0, a.length - 1 );
}

/**
 * Internal method that makes recursive calls.
 * @param a an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param left the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 */
private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
        int left, int right ) {
    if( left < right ) {
        int center = ( left + right ) / 2;
        mergeSort( a, tmpArray, left, center );
        mergeSort( a, tmpArray, center + 1, right );
        merge( a, tmpArray, left, center + 1, right );
    }
}

/**
 * Internal method that merges two sorted halves of a subarray.
 * @param a an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param leftPos the left-most index of the subarray.
 * @param rightPos the index of the start of the second half.
 * @param rightEnd the right-most index of the subarray.
 */
private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
        int leftPos, int rightPos, int rightEnd ) {
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    // Main loop
    while( leftPos <= leftEnd && rightPos <= rightEnd )
        if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        else
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

    while( leftPos <= leftEnd )    // Copy rest of first half
        tmpArray[ tmpPos++ ] = a[ leftPos++ ];

    while( rightPos <= rightEnd )  // Copy rest of right half
        tmpArray[ tmpPos++ ] = a[ rightPos++ ];

    // Copy tmpArray back
    for( int i = 0; i < numElements; i++, rightEnd-- )
        a[ rightEnd ] = tmpArray[ rightEnd ];
}

Answer 3

O notation describes a limiting behaviour of a function, a worst case for an algorithm. Usually it's sufficient to compare different algorithms for the same task, like sorting algorithms by that function.

I'd say, for almost all algorithms (except O(1) algorithms ;) ) there's always some input data that makes the algorithm terminate in less time (or with less memory consumption) then indicated by the describing O notation for that algorithm.

Assume we have a counting algorithm like that:

private int counter(int n) {
  int counter;
  for (int i = 0; i < 2; i++) {
    counter = 0;
    for (int i = 0; i < n; i++) {
      counter++;
    }
  }
  return counter;
}

The growth is linear, so the O notation for this counter is O(n) (I'm only looking at steps, not memory). You could argue that, hey, we're counting twice, and write O(2n) instead. True. You could even write O(2n+c) to indicate that we need some extra steps (time) to create and initialize the local variable.

Here is an improved implementation, that still is linear (O(n)) but terminates significantly faster:

private int counter(int n) {
  int counter =0;
  for (int i = 0; i < n; i++) {
    counter++;
  }
  return counter;
}

Both can be described as O(n) to indicate linear growth. That may be sufficient, for example to compare these implementations with an O(n^2) or O(1) implementation of that counter. But to compare the 'linear' versions A and B, we need to be more precise and identify the first one as O(2n) and the second as O(n). Now the comparison of the to O notation values gives the expected result: implementation B is 'better'.

Answer 4

Couldn't one invert part of the question? So that taking a version that runs smoothly, make it more inefficient but in a way that doesn't change the big-O of the original code. For example, adding a line so the program sleeps for 10 seconds while performing some work is a constant time change which would be removed when computing the big-O, I think. In this case, the version with the extra code would be version 1 while the other is version 2 which is more efficient but in an inconsequential form.

If one wants an answer in a bit more abstract sense, because big-O ignores lower order terms and constant multipliers, these can be where one can make something more efficient without changing the overall big-O of a method. I'm sorry this doesn't have any Java code but this answer is language-agnostic this way.