AP Computer Science A
Advanced Placement Computer Science A focusing on Java programming and object-oriented design.
Advanced Topics
Algorithm Analysis and Sorting
How Fast is Your Code?
Not all code is created equal! Some algorithms solve problems faster than others.
Big O Notation
Big O notation describes how the runtime of an algorithm grows as the input size increases.
- \( O(n) \): Linear — time increases with input.
- \( O(n^2) \): Quadratic — time grows much faster.
Sorting Algorithms
Sorting puts elements in order. Common algorithms include:
- Selection Sort: Finds the smallest element and moves it to the front.
- Insertion Sort: Builds a sorted list one item at a time.
// Simple selection sort
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[min]) min = j;
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
Why This Matters
Efficient algorithms save time and make programs run smoothly—essential for apps, games, and websites!
Examples
Comparing \( O(n) \) and \( O(n^2) \) algorithms for sorting a list.
Using selection sort to order student grades.
In a Nutshell
Algorithm analysis helps you write faster, more efficient code.