Big O Notations

Big O NotationsWelcome to my Big O Notations tutorial. Big O notations are used to measure how well a computer algorithm scales as the amount of data involved increases. It isn’t however always a measure of speed as you’ll see.

This is a rough overview of Big O and I hope to simplify it rather than get into all of the complexity. I’ll specifically cover the following O(1), O(N), O(N^2), O(log N) and O(N log N). Between the video and code below I hope everything is completely understandable.

If you like videos like this, it helps to tell Google+

Code From the Video

Big O Notations

// Big O notation is a way to measure how well a
// computer algorithm scales as the amount of data
// involved increases. It is not always a measure
// of speed as you'll see below

// This is a rough overview of Big O and doesn't 
// cover topics such as asymptotic analysis, which
// covers comparing algorithms as data approaches
// infinity

// What we are defining is the part of the algorithm 
// that has the greatest effect. For example
// 45n^3 + 20n^2 + 19 = 84 (n=1)
// 45n^3 + 20n^2 + 19 = 459 (n=2) Does 19 matter?
// 45n^3 + 20n^2 + 19 = 47019 (n=10) 
// Does the 20n^2 matter if 45n^3 = 45,000?
// Has an O(n^3) Order of n-cubed

public class BigONotation {

	private int[] theArray;

	private int arraySize;

	private int itemsInArray = 0;

	static long startTime;

	static long endTime;

	public static void main(String[] args) {

		/*
		 * 0(1) Test BigONotation testAlgo = new BigONotation(10);
		 * 
		 * testAlgo.addItemToArray(10);
		 * 
		 * System.out.println(Arrays.toString(testAlgo.theArray));
		 */

		BigONotation testAlgo2 = new BigONotation(100000);
		testAlgo2.generateRandomArray();

		BigONotation testAlgo3 = new BigONotation(200000);
		testAlgo3.generateRandomArray();

		BigONotation testAlgo4 = new BigONotation(30000);
		testAlgo4.generateRandomArray();

		BigONotation testAlgo5 = new BigONotation(400000);
		testAlgo5.generateRandomArray();

		/*
		 * O(N) Test
		 * 
		 * testAlgo2.linearSearchForValue(20);
		 * 
		 * testAlgo3.linearSearchForValue(20);
		 * 
		 * testAlgo4.linearSearchForValue(20);
		 * 
		 * testAlgo5.linearSearchForValue(20);
		 */

		// O(N^2) Test
		/*
		 * testAlgo2.bubbleSort();
		 * 
		 * testAlgo3.bubbleSort();
		 * 
		 * testAlgo4.bubbleSort();
		 * 
		 * // 0 (log N) Test
		 * 
		 * testAlgo2.binarySearchForValue(20);
		 * testAlgo3.binarySearchForValue(20);
		 */

		// O (n log n) Test

		startTime = System.currentTimeMillis();

		testAlgo2.quickSort(0, testAlgo2.itemsInArray);

		endTime = System.currentTimeMillis();

		System.out.println("Quick Sort Took " + (endTime - startTime));

	}

	// O(1) An algorithm that executes in the same
	// time regardless of the amount of data
	// This code executes in the same amount of
	// time no matter how big the array is

	public void addItemToArray(int newItem) {

		theArray[itemsInArray++] = newItem;

	}

	// 0(N) An algorithm thats time to complete will
	// grow in direct proportion to the amount of data
	// The linear search is an example of this

	// To find all values that match what we
	// are searching for we will have to look in
	// exactly each item in the array

	// If we just wanted to find one match the Big O
	// is the same because it describes the worst
	// case scenario in which the whole array must
	// be searched

	public void linearSearchForValue(int value) {

		boolean valueInArray = false;
		String indexsWithValue = "";

		startTime = System.currentTimeMillis();

		for (int i = 0; i < arraySize; i++) {

			if (theArray[i] == value) {
				valueInArray = true;
				indexsWithValue += i + " ";
			}

		}

		System.out.println("Value Found: " + valueInArray);

		endTime = System.currentTimeMillis();

		System.out.println("Linear Search Took " + (endTime - startTime));

	}

	// O(N^2) Time to complete will be proportional to
	// the square of the amount of data (Bubble Sort)
	// Algorithms with more nested iterations will result
	// in O(N^3), O(N^4), etc. performance

	// Each pass through the outer loop (0)N requires us
	// to go through the entire list again so N multiplies
	// against itself or it is squared

	public void bubbleSort() {

		startTime = System.currentTimeMillis();

		for (int i = arraySize - 1; i > 1; i--) {

			for (int j = 0; j < i; j++) {

				if (theArray[j] > theArray[j + 1]) {

					swapValues(j, j + 1);

				}
			}
		}

		endTime = System.currentTimeMillis();

		System.out.println("Bubble Sort Took " + (endTime - startTime));
	}

	// O (log N) Occurs when the data being used is decreased
	// by roughly 50% each time through the algorithm. The
	// Binary search is a perfect example of this.

	// Pretty fast because the log N increases at a dramatically
	// slower rate as N increases

	// O (log N) algorithms are very efficient because increasing
	// the amount of data has little effect at some point early
	// on because the amount of data is halved on each run through

	public void binarySearchForValue(int value) {

		startTime = System.currentTimeMillis();

		int lowIndex = 0;
		int highIndex = arraySize - 1;

		int timesThrough = 0;

		while (lowIndex <= highIndex) {

			int middleIndex = (highIndex + lowIndex) / 2;

			if (theArray[middleIndex] < value)
				lowIndex = middleIndex + 1;

			else if (theArray[middleIndex] > value)
				highIndex = middleIndex - 1;

			else {

				System.out.println("\nFound a Match for " + value
						+ " at Index " + middleIndex);

				lowIndex = highIndex + 1;

			}

			timesThrough++;

		}

		// This doesn't really show anything because
		// the algorithm is so fast

		endTime = System.currentTimeMillis();

		System.out.println("Binary Search Took " + (endTime - startTime));

		System.out.println("Times Through: " + timesThrough);

	}

	// O (n log n) Most sorts are at least O(N) because
	// every element must be looked at, at least once.
	// The bubble sort is O(N^2)
	// To figure out the number of comparisons we need
	// to make with the Quick Sort we first know that
	// it is comparing and moving values very
	// efficiently without shifting. That means values
	// are compared only once. So each comparison will
	// reduce the possible final sorted lists in half.
	// Comparisons = log n! (Factorial of n)
	// Comparisons = log n + log(n-1) + .... + log(1)
	// This evaluates to n log n

	public void quickSort(int left, int right) {

		if (right - left <= 0)
			return;

		else {

			int pivot = theArray[right];

			int pivotLocation = partitionArray(left, right, pivot);

			quickSort(left, pivotLocation - 1);
			quickSort(pivotLocation + 1, right);

		}

	}

	public int partitionArray(int left, int right, int pivot) {

		int leftPointer = left - 1;
		int rightPointer = right;

		while (true) {

			while (theArray[++leftPointer] < pivot)
				;

			while (rightPointer > 0 && theArray[--rightPointer] > pivot)
				;

			if (leftPointer >= rightPointer) {

				break;

			} else {

				swapValues(leftPointer, rightPointer);

			}

		}

		swapValues(leftPointer, right);

		return leftPointer;

	}

	BigONotation(int size) {

		arraySize = size;

		theArray = new int[size];

	}

	public void generateRandomArray() {

		for (int i = 0; i < arraySize; i++) {

			theArray[i] = (int) (Math.random() * 1000) + 10;

		}

		itemsInArray = arraySize - 1;

	}

	public void swapValues(int indexOne, int indexTwo) {

		int temp = theArray[indexOne];
		theArray[indexOne] = theArray[indexTwo];
		theArray[indexTwo] = temp;

	}

}

23 Responses to “Big O Notations”

  1. Steven says:

    Thanks Derek. Great video as usual. I have a problem. Can you please help me ?
    I need to extract text from 3rd-party applications. Something like when I chat on yahoo messenger, I need to extract the text and display it on my own application.

    I know it’s outside of this tutorial but can you please help ? thank you thank you thank you 🙂

  2. Antony Jawili says:

    Hi Derek,

    Geat presentation. This video is really helpful however your a liitle bit fast but you teach very well. Maybe in your next presentation hoping you can do itlittle bit slower it ok with you, if not it’s fine too.

    Anaway, I did try your code but I’m getting error with static time long variables. “Illegal modifier for parameter starTime and endTime. Do you have any idea?

    Thanks,
    Anthony

    • Derek Banas says:

      Thank you 🙂 I’m trying to make the videos as understandable as possible while also keeping them from getting boring. You may have noticed that I have recently slowed down a bit.

      As per the error, there must be a typo some place. I noticed you typed starTime instead of startTime? You often see that error when you try to set visibility scopes (private, protected, etc) for local variables. I hope that helps

  3. Harsha says:

    Hi Derek

    Excellent video on BigO notations !!

    Regards
    Harsha

  4. John says:

    Great video Derek

  5. Venkat says:

    Hi Derek,

    Very good video and providing good ontroduction to Big O notation.
    Thanks you very much for posting the video.

    Thanks,
    Venkat.

  6. Empress says:

    Hi Derek!

    I just wanted to review important lessons from my Data Structure class and your video taught me a lot of new things I didn’t knew.

    Great video, I hoped my Data Structure professor would give the right name for this topic when he introduced the class to measure how an algorithm scales.

  7. mattz says:

    Hi Derek,
    I have not gone back to school in 10 years! And I have been working in the tech industry for a while now…These videos of yours are just amazing and i wish my profs at school had taught with such enthusiasm. I have decided to study every day a little bit to keep myself in tune with the basics of Computer Science! Thanks and pls keep posting these!

  8. aaron says:

    hi derek, may i ask about log(n!) as well as notations of exponential time. e.g. is 2^n+1 the same as 2^n

    Regards

  9. Imtiaz says:

    Hi Derek,

    Big fan of your tutorials. One of my prof at college for design pattern course used to play your video in the class. Your video was more clear then prof’s lecture.

  10. SCHOW says:

    Hey Derek,

    I am looking for a tutor. I was hoping I could find someone online. I understand your videos really well. Do you think you could help?

    SCHOW

  11. ronna parra says:

    can you give me an example of BIG O notation?

Leave a Reply

Your email address will not be published.

Google+