Explain the big O of this algorithm: if(array.length < 2) return; int iValue = 0

Question

Explain the big O of this algorithm:

       if(array.length < 2)

           return;

       int iValue = 0;

       int jValue = array[1];

       int jIndex = 1;

       int iIndex = 0;

       int maxDWF = 0;

       int tempDWF = 0;

       int maxI = 0;

       int maxJ = 0;

       int len = (array.length - 1);

       for(int k = 0; k < array.length - 1; k++) {

           for(int m = 0; m < len; m++) {

               iIndex = k;

               iValue = array[k];

               System.out.println(Math.abs(iValue - jValue) / Math.abs(iIndex - jIndex));

               tempDWF = Math.abs(iValue - jValue) / Math.abs(iIndex - jIndex);

               if(tempDWF > maxDWF) {

                   maxDWF = tempDWF;

                   maxI = iIndex;

                   maxJ = jIndex;

               }

               if(jIndex < array.length - 1)

                   jIndex++;

               jValue = array[jIndex];

           }

           if(len == 1)

               break;

           jValue = array[k + 2];

           jIndex = k + 2;

           len--;

       }

I know that the big O is within O(n^2) but need help explaining why

Explanation / Answer

One way of determining the big-O value (an algorithm's order) is to start out assuming an order of O (1), an algorithm that doesn't do anything and immediately terminates no matter what the input. Then, find the part of code that you expect to have the highest order. From there, work out the algorithmic efficiency from the outside in-- then figure out the efficiency of the outer loop or recursive portion of the code, then find the efficiency of the inner code; the total efficiency is the efficiency of each layer of code multiplied together.

Based on the above program we can compute that the order of the outer loop (for (int k = 0; k < array.length - 1; k++) is O(n);

Hope now you understood why it is

Now, we can compute that the order of the inner loop is roughly O(n). Note that even though its efficiency varies based on the value of k, the average efficiency is n/2, and we ignore the constant, so it's O(n). After multiplying together the order of the outer and the inner loop, we have O (n^2).

In order to use this approach effectively, one should be able to deduce the order of the various steps of the algorithm. And you won't always have a piece of code to look at; sometimes you may want to just discuss a concept and determine its order.

O (n)

Algorithms of efficiency n require only one pass over an entire input. For example, a linear search algorithm, which searches an array by checking each element in turn, is O(n). Often, accessing an element in a linked list is O(n) because linked lists do not support random access.

O (n^2)

A good reasonable efficiency, still in the polynomial time range, the typical examples for this order come from sorting algorithms.

Hope now you understood why this algorithm is O (n^2) based on the above explanation.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

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