Big O Notation

Question 1

Bubble Sort

Answer 1

Worst Case: O(n^2)
Best Case: O(n)

• Starting on the left, compare adjacent items and keep “bubbling”/moving the larger one to the right (so that it’s in its final place).
• Bubble sort the remaining N -1 items until the array is sorted

Question 2

Insertion Sort

Answer 2

Worst Case: O(n^2)
Best Case: O(n)

• Start with a sorted list of 1 element on the left, and N-1 unsorted items on the right.
• Take the first unsorted item, [i] = 1, insert it into the sorted list, moving elements as necessary.
• We now have a sorted list of size 2, and N -2 unsorted elements. Repeat for all elements.

Question 3

Selection Sort

Answer 3

Worst Case & Best Case: O(n^2)

• Scan all items and find the smallest.
• Swap it into position as the first item.
• Repeat the selection sort on the remaining N-1 items.

Question 4

Quick Sort

Answer 4

Worst Case: O(n^2)
Average & Best: O(n log n)

The “Divide and Conquer” Algorithm

• Choose a ‘pivot’ (middle) value.
• Put all value less than the pivot in the left part of the array, then the pivot itself, then all values greater than the pivot.
• Recursively, sort the values less than the pivot.
• Recursively, sort the values greater than the pivot.
• Combine the lists, the entire list will be sorted.

Question 5

Heap Sort

Answer 5

Worst/Average/Best Case: O(n log n)

• Add all items into a heap.
• Pop the largest item from the heap and insert it in the final position.
• Repeat for all items

WHY (n log n)?
–> Creation of the heap is O(n log n).
–> Popping items is O(1),
- Fixing the heap after the pop is O(log n),
- AND there are n pops
- So there is another O(n log n) factor.
Thus, O(n log n) overall.

Question 6

Counting Sort

Answer 6

Worst/Average/Best Case: O(n)

• Create an array of size n to keep track of how many items appear (ie. 3 items with value 0, 4 items with value 1, etc).
• Given this count, you can tell the position of an item — all 1’s must come after 0’s, of which there are 3.
• Therefore, 1’s start at item #4.
• Thus, we can scan the items and insert them into their proper position.

O(n) since every step is O(n).