Very Short Look at the Big O and Nested For Loops

Big O notation is used to indicate the runtime of an algorithm as it processes large amounts of data, in which case the determining factor of the execution time is the term with the largest exponent, ignoring all other terms and even the coefficient as the data set to be processed grows extremely large. Big O notation therefore drops the constants, which can be confusing.

#include <time.h>
#include <stdlib.h>

void populateArray(int array[], int size, int num_max);
void printArray(int arrayParam[], int size);
void minMaxA(int iArray[], int size, int num_max);
void minMaxB(int iArray[], int size, int num_max);

int main() {
	
	const int array_size = 2056;
	const int num_max = 7800;

	int iArray[array_size];
	int iMax = 0;

	populateArray(iArray, array_size, num_max);
	printArray(iArray, array_size);

	minMaxA(iArray, array_size, num_max);
	minMaxB(iArray, array_size, num_max);

	return 0;

}

void printArray(int arrayParam[], int size) {
	int *iArray = arrayParam;
	for (int i = 0; i < size; i++) {
		printf("%d ", *iArray++);
	}
}

//populate the array with random numbers
void populateArray(int array[], int size, int num_max) {
	srand(time(NULL));
	for (int i = 0, x = 0; i < size; i++) {
		x = rand() % num_max;
		array[i] = x;
	}
}

//one loop 
void minMaxA(int iArray[], int size, int num_max) {
	int iMin = num_max;
	int iMax = 0;
	for (int i = 0; i < size; i++) {
		//check for minimum 
		if (iArray[i] < iMin) { iMin = iArray[i]; } 		       //check for maximum 		
                if (iArray[i] > iMax) { iMax = iArray[i]; }
	}

	printf("\nThe maximum value is %d\n\n", iMax);
	printf("\nThe minimum value is %d\n\n", iMin);
}

//two loops
void minMaxB(int iArray[], int size, int num_max) {
	//start search from highest value
	int iMin = num_max;
	//start search from lowest value
	int iMax = 0;
	//loop one
	for (int i = 0; i < size; i++) {
		if (iArray[i] < iMin) { iMin = iArray[i]; }
	}
	//loop two
	for (int i = 0; i < size; i++) { 		
                if (iArray[i] > iMax) { iMax = iArray[i]; }
	}

	printf("\nThe maximum value is %d\n\n", iMax);
	printf("\nThe minimum value is %d\n\n", iMin);
}


Note that the minMaxA() and minMaxB() functions have the same time complexity, since we drop the coefficient. Likewise, we drop all other other non-dominant terms, meaning that the term or terms with the largest exponents are the only ones that we need to concern ourselves with.

void printSumProducts(int iArray[], int length);

int main() {
	
	int iArray[7] = {73, 4, 8, 15, 16, 23, 42 };
	printSumProducts(iArray, 7);

	return 0;

}


//this function takes O(2) time
//the fact that it loops twice is irrelevant 
void printSumProducts(int iArray[], int length) {
	long long int sum = 0;
	//initialize product to 1, not 0
	long long int product = 1;

	for (int i = 0; i < length; i++) {
		sum += iArray[i];
	}

	for (int i = 0; i < length; i++) {
		product *= iArray[i];
	}

	printf("Sum of the array: %lld\n", sum);
	printf("Product of the array: %lld\n", product);

}

Runtimes tend to increase as loops are called within loops. For example, a nested loop that iterates through the entire list once for each loop as O(n^2) time.

void printPairs(int iArray[], int arraySize);
void printUnorderedPairs(int iArray[], int arraySize);

int main() {
	
	const int array_size = 10;

	int iArray[array_size] = { 1138, 151, 191, 47, 353, 383, 16, 32, 64, 128 };

	printPairs(iArray, array_size);

	printf("\n\n");

	printUnorderedPairs(iArray, array_size);

	return 0;

}

//both of these functions take O(n^2) time
void printPairs(int iArray[], int arraySize) {
	int iNumPairs = 0;
	for (int i = 0; i < arraySize; i++) { 		
           for (int j = arraySize - 1; j >= 0; j--) {
			printf("(%d, %d) \t", iArray[i], iArray[j]);
			iNumPairs++;
		}
		printf("\n");
	}
	printf("Printed %d pairs total.\n", iNumPairs);
}

//inner loop starts at i + 1
//stil takes O(n^2) time
void printUnorderedPairs(int iArray[], int arraySize) {
	int iNumPairs = 0;
	for (int i = 0; i < arraySize; i++) {
		for (int j = i + 1; j < arraySize; j++) {
			printf("(%d, %d) \t", iArray[i], iArray[j]);
			iNumPairs++;
		}
		printf("\n");
	}
	printf("Printed %d pairs total.\n", iNumPairs);
}

Even though the second function performs roughly half as many operations as the first, it still has the same time complexity.

Another illustration of this is given with the following code, which contains a function that reverses an array.

void reverseArray(int array[], int lengthParam);
void printArray(int array[], int length);

int main() {
	
	const int array_length = 11;

	int iArray[array_length] = { 10538, 1, 451, 47, 1865, 73, 6174, 1701, 2001, 8675309, 8086 };

	printArray(iArray, array_length);
	reverseArray(iArray, array_length);
	printArray(iArray, array_length);

	return 0;

}


void reverseArray(int array[], int lengthParam) {
	int halfLength = lengthParam / 2;
	int temp;
	for (int i = 0, j = lengthParam - 1; i < halfLength; i++) {
		temp = array[i];
		array[i] = array[j - i];
		array[j - i] = temp;
	}
}

void printArray(int array[], int length) {
	for (int i = 0; i < length; i++) {
		printf("%d ", array[i]);
	}
	printf("\n\n");
}

Even though our reverseArray() function only goes through half of the array, or less, the big O time is still considered to be O(n).

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s