C949 Study Guide Highlighted Topics

Finiteness

An algorithm must always have a finite number of steps before it ends. It must have a defined endpoint and not enter an endless loop.

Definiteness

An algorithm needs exact definitions for each step. Every step should be clear and unambiguous.

Modularity

Breaking a problem into small modules or small steps.

Extensibility

An algorithm should be reusable and extendable by other programmers.

Base Case

The condition under which recursion stops; the simplest instance solved without further recursion.

Linear Search Best Case

O(1) — The target element is the first element.

Linear Search Average Case

O(n) — The target element is somewhere in the middle or not in the array.

Linear Search Worst Case

O(n) — The target element is the last element or not present.

Binary Search Concept

Operates on a sorted list and repeatedly divides the search interval in half.

Binary Search Time Complexity

O(log n)

Binary Search Use Case

Ideal for large sorted datasets.

Binary Search Requirement

Requires a sorted array.

Binary Search Characteristic

Divides the search interval in half repeatedly.

Binary Search Best Case

O(1) — The target element is the middle element.

Binary Search Average Case

O(log n)

Binary Search Worst Case

O(log n)

Bubble Sort Use Case

Simple but inefficient; best for education or small lists.

Bubble Sort Characteristic

Repeatedly swaps adjacent elements that are in the wrong order.

Bubble Sort Characteristic

Largest element bubbles to the end of the list.

Bubble Sort Best Case

O(n)

Bubble Sort Average Case

O(n²)

Bubble Sort Worst Case

O(n²)

Bubble Sort Clue

Swap, Exchange, Bubble

Selection Sort Use Case

Useful when memory writes are more expensive than comparisons.

Selection Sort Characteristic

Finds the minimum element and swaps it with the first unsorted element.

Selection Sort Characteristic

Reduces the problem size by one each iteration.

Selection Sort Best Case

O(n²)

Selection Sort Average Case

O(n²)

Selection Sort Worst Case

O(n²)

Selection Sort Clue

Select Minimum, Swap With Start

Insertion Sort Use Case

Good for small or nearly sorted lists.

Insertion Sort Characteristic

Builds a sorted list one element at a time.

Insertion Sort Characteristic

Shifts elements to make space for the current element.

Insertion Sort Best Case

O(n)

Insertion Sort Average Case

O(n²)

Insertion Sort Worst Case

O(n²)

Insertion Sort Clue

Insert, Shift Element

Merge Sort Use Case

Efficient and stable for large datasets.

Merge Sort Characteristic

Divides the list into halves, sorts each half, then merges them.

Merge Sort Characteristic

Requires additional space for merging.

Merge Sort Best Case

O(n log n)

Merge Sort Average Case

O(n log n)

Merge Sort Worst Case

O(n log n)

Merge Sort Clue

Merge, Split

Quicksort Use Case

Often faster in practice than merge sort but less stable.

Quicksort Characteristic

Uses a pivot element and partitions the array.

Quicksort Characteristic

Recursively sorts partitions.

Quicksort Best Case

O(n log n)

Quicksort Average Case

O(n log n)

Quicksort Worst Case

O(n²)

Quicksort Clue

Pivot, Split

Heap Sort Use Case

Useful when memory usage is a concern because it is in-place.

Heap Sort Characteristic

Uses a binary heap data structure.

Heap Sort Characteristic

Builds a max heap and repeatedly extracts the maximum element.

Heap Sort Best Case

O(n log n)

Heap Sort Average Case

O(n log n)

Heap Sort Worst Case

O(n log n)

Heap Sort Clue

Heapify, Extract Max, Build Heap

Counting Sort Use Case

Efficient for sorting integers with a small range of values.

Counting Sort Characteristic

Counts occurrences of each element.

Counting Sort Characteristic

Non-comparative sorting algorithm.

Counting Sort Best Case

O(n + k)

Counting Sort Average Case

O(n + k)

Counting Sort Worst Case

O(n + k)

Radix Sort Use Case

Effective for sorting large numbers or fixed-length strings.

Radix Sort Characteristic

Processes individual digits.

Radix Sort Characteristic

Often combined with counting sort.

Radix Sort Best Case

O(n × k)

Radix Sort Average Case

O(n × k)

Radix Sort Worst Case

O(n × k)

Radix Sort Clue

Count, Frequency, Sum

Bucket Sort Use Case

Good for uniformly distributed data.

Bucket Sort Characteristic

Distributes elements into buckets and sorts each bucket.

Bucket Sort Characteristic

Often combined with insertion sort.

Bucket Sort Best Case

O(n + k)

Bucket Sort Average Case

O(n + k)

Bucket Sort Worst Case

O(n²)

Bucket Sort Clue

Bucket

Shell Sort Characteristic

Generalization of insertion sort using a gap sequence.

Shell Sort Characteristic

Sorts elements far apart and gradually reduces the gap.

Shell Sort Time Complexity

Commonly O(n^1.5)

Shell Sort Best Case

O(n log n)

Shell Sort Average Case

O(n^1.5)

Shell Sort Worst Case

O(n²)

Shell Sort Clue

Gap, Interval

O(1)

Constant Time

O(log n)

Logarithmic Time

O(n)

Linear Time

O(n log n)

Log-Linear Time

O(n²)

Quadratic Time

O(2^n)

Exponential Time

O(n!)

Factorial Time

O(1) Example

Accessing an array element by index.

O(log n) Example

Binary Search.

O(n) Example

Linear Search.

O(n log n) Example

Merge Sort, Quicksort, Heap Sort.

O(n²) Example

Bubble Sort, Insertion Sort, Selection Sort.

O(2^n) Example

Recursive Fibonacci.

O(n!) Example

Traveling Salesman brute force.

Pre-Order Traversal

NLR (Node, Left, Right)