Computation Complexity - Double Loop

Given a sorted array in descending order, following code counts pairs of two elements with the difference d. It is easy to give an O(n²) bound for the time complexity of the function countingDifference in below codes; n times in outer for-loop and n times inner while-loop.

But a more careful analysis shows that in fact we can give an O(2n) = O(n) bound on the time complexity of this functions.  The command j++; is executed no more than n times totally, while outer for-loop is looping n times.  So, time complexity of this function is O(n+n) = O(2n) = O(n). 

The statement 'this function(algorithm) is O(n²)' is still right. 'this algorithm is O(n)' gives more information about the function.

public class CodeTest {
static int counter1 =0;
static int counter2 =0;

public static void main(String[] args) {
int input[] = {112, 39, 34, 32, 30, 27, 12, 11, 9, 8, 5, 2, 0};
int d = 2;

System.out.print("Input: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");
System.out.println();
System.out.println( "For " + input.length + " -length array: " + countDiffernce(input, d) + " pairs are " + d + "-differences " );
System.out.println ("Outer Loop: " + counter1 + " times, Inner Loop: " + counter2 + " times");
}

public static int countDiffernce(int input[], int d) {
int cnt =0, n = input.length;
int j = 1;
for (int i = 0; i < n && j < n; i++) {
counter1++;
while ( (j < n-1) && (input[i] - input[j] < d)) {
counter2++;
j++;
}
if(input[i] - input[j] == d) {
cnt++;
System.out.println("\t" + input[i] + " - " + input[j] + " = " + d);
} 
}
return cnt;
}
}

Read more »

Posted in: Big O,Computation Complexity,Java,Programming,Time Complexity

Insertion Sort in Java/C of an Integer Array

Average Performance: О(n²)
Best Case Performance:О(n)
Worst Case Performance: О(n²)
Classification: stable, in-place, online

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: [from Wiki]

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

Below source code is written in Java, but you can use the function insertionSort() without any modification. Just write your main() function with input array and call insertionSort() with two parameters: array and array size.

public class CodeTest {
static int counter1 =0;
static int counter2 =0;

public static void main(String[] args) {
int input[] = {94,34,53,21,100,102, 21, 53,45, 456, 3, 32,1,5,4};

System.out.print("Before Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

insertionSort(input, input.length);

System.out.print("\nAfter Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

System.out.println("\n Outerfor loop: " + counter1 + " times, inner while loop: " + counter2 + " times");
}

public static void insertionSort(int input[], int length) {
int i, j, key;

for(i = 1; i<length;i++) {
counter1++;
key = input[i];
j = i - 1;

while (j>=0 && input[j] > key) {
counter2++;
input[j+1] = input[j];
j--;
}
input[j+1] = key;
}
}
}

Read more »

Posted in: C,Insertion Sort,Java,Programming,sorting algorithm