AP Computer Science Principles Flashcards: Algorithmic Efficiency

What this deck covers

This deck focuses on Algorithmic Efficiency, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science Principles.

How to use these flashcards

Work through these flashcards in short sessions. Try to answer each prompt before flipping the card, then revisit any cards you miss until the explanation feels automatic.

Flashcard 1: Identify the Big O notation for insertion sort in the best case.

Answer: $O(n)$. Already sorted array requires only single pass.

Flashcard 2: Identify the Big O notation for matrix multiplication.

Answer: $O(n^3)$. Three nested loops for standard multiplication algorithm.

Flashcard 3: What is the time complexity of heap sort?

Answer: $O(n \text{ log } n)$. Maintains heap property through logarithmic operations.

Flashcard 4: Identify the time complexity of the Bellman-Ford algorithm.

Answer: $O(VE)$. Relaxes edges multiple times across all vertices.

Flashcard 5: What is the Big O notation for an algorithm with constant time?

Answer: $O(1)$. Operation takes same time regardless of input size.

Flashcard 6: What is the definition of algorithmic efficiency?

Answer: Algorithmic efficiency measures resource usage. Focuses on time and space usage as performance metrics.

Flashcard 7: What does Big O notation describe?

Answer: It describes the upper limit of an algorithm's complexity. Represents worst-case performance as input size grows.

Flashcard 8: State the Big O notation for searching an unsorted list.

Answer: $O(n)$. Must examine every element without ordering advantage.

Flashcard 9: Identify the time complexity of Kruskal's algorithm.

Answer: $O(E \text{ log } E)$. Sorting edges dominates the union-find operations.

Flashcard 10: Find the time complexity of the worst case of bubble sort.

Answer: $O(n^2)$. Compares adjacent pairs through nested iterations.

Flashcard 11: State the Big O notation for the worst case of quicksort.

Answer: $O(n^2)$. Poor pivot selection leads to unbalanced partitions.

Flashcard 12: State the time complexity of selection sort.

Answer: $O(n^2)$. Nested loops to find minimum and swap elements.

Flashcard 13: Identify the Big O notation for matrix multiplication.

Answer: $O(n^3)$. Three nested loops for standard multiplication algorithm.

Flashcard 14: Identify the time complexity of Kruskal's algorithm.

Answer: $O(E \text{ log } E)$. Sorting edges dominates the union-find operations.

Flashcard 15: Identify the Big O notation for a bubble sort algorithm.

Answer: $O(n^2)$. Nested loops create quadratic growth pattern.

Flashcard 16: State the Big O notation for a binary search algorithm.

Answer: $O(\text{log } n)$. Eliminates half of remaining elements each iteration.

Flashcard 17: State the Big O notation for a binary search algorithm.

Answer: $O(\text{log } n)$. Eliminates half of remaining elements each iteration.

Flashcard 18: State the Big O notation for an exponential time algorithm.

Answer: $O(2^n)$. Runtime doubles with each additional input element.

Flashcard 19: Find and correct the error: 'A binary search has $O(n)$ complexity.'

Answer: Correct: 'A binary search has $O(\text{log } n)$ complexity.'. Binary search divides search space logarithmically.

Flashcard 20: Identify the time complexity for depth-first search (DFS).

Answer: $O(V + E)$. Visits each vertex and edge exactly once.

Flashcard 21: What is the time complexity of a naive string matching algorithm?

Answer: $O(nm)$, where $n$ is text length and $m$ is pattern length. Compares pattern at every possible text position.

Flashcard 22: Find and correct the error: 'The time complexity of merge sort is $O(n^2)$.'

Answer: Correct: 'The time complexity of merge sort is $O(n \text{ log } n)$.'. Merge sort consistently divides and merges efficiently.

Flashcard 23: What is the space complexity of an algorithm?

Answer: It measures the memory usage of an algorithm. Tracks additional storage beyond input data.

Flashcard 24: What is the space complexity of breadth-first search (BFS)?

Answer: $O(V)$. Queue size bounded by number of vertices.

Flashcard 25: State the Big O notation for a depth-first search (DFS) space complexity.

Answer: $O(V)$. Recursion stack depth limited by vertex count.

Flashcard 26: What is the Big O notation for an algorithm with logarithmic time complexity?

Answer: $O(\text{log } n)$. Search space halves with each comparison step.

Flashcard 27: What is the time complexity of a naive string matching algorithm?

Answer: $O(nm)$, where $n$ is text length and $m$ is pattern length. Compares pattern at every possible text position.

Flashcard 28: Identify the time complexity of a hash table search operation.

Answer: $O(1)$. Direct access through hash function calculation.

Flashcard 29: What is the average case time complexity of quicksort?

Answer: $O(n \text{ log } n)$. Balanced partitioning creates optimal divide-and-conquer.

Flashcard 30: State the Big O notation for searching an unsorted list.

Answer: $O(n)$. Must examine every element without ordering advantage.

Flashcard 31: What is the time complexity of Dijkstra's algorithm?

Answer: $O(V^2)$. Uses adjacency matrix for dense graph representation.

Flashcard 32: Identify the Big O notation for the best case of quicksort.

Answer: $O(n \text{ log } n)$. Good pivot creates balanced recursive partitions.

Flashcard 33: What is the space complexity of an algorithm?

Answer: It measures the memory usage of an algorithm. Tracks additional storage beyond input data.

Flashcard 34: What is the time complexity of heap sort?

Answer: $O(n \text{ log } n)$. Maintains heap property through logarithmic operations.

Flashcard 35: What is the Big O notation for an algorithm with constant time?

Answer: $O(1)$. Operation takes same time regardless of input size.

Flashcard 36: What does Big O notation describe?

Answer: It describes the upper limit of an algorithm's complexity. Represents worst-case performance as input size grows.

Flashcard 37: What is the time complexity of a merge sort algorithm?

Answer: $O(n \text{ log } n)$. Divide-and-conquer with linear merge operations.

Flashcard 38: Which algorithm has a time complexity of $O(n)$?

Answer: Linear search algorithm. Checks each element once in worst case.

Flashcard 39: What is the Big O notation for Fibonacci sequence using recursion?

Answer: $O(2^n)$. Each call branches into two recursive calls.

Flashcard 40: What is the Big O notation for Fibonacci sequence using recursion?

Answer: $O(2^n)$. Each call branches into two recursive calls.

Flashcard 41: Identify the Big O notation for a bubble sort algorithm.

Answer: $O(n^2)$. Nested loops create quadratic growth pattern.

Flashcard 42: What is the worst-case time complexity of insertion sort?

Answer: $O(n^2)$. Comparisons increase quadratically for reverse-sorted input.

Flashcard 43: Identify the Big O notation for insertion sort in the best case.

Answer: $O(n)$. Already sorted array requires only single pass.

Flashcard 44: What does the term 'polynomial time' mean in algorithmic complexity?

Answer: It means time complexity is $O(n^k)$ for constant $k$. Runtime bounded by polynomial function of input size.

Flashcard 45: What is the time complexity of the Floyd-Warshall algorithm?

Answer: $O(n^3)$. All-pairs shortest path with triple nested loops.

Flashcard 46: What is the time complexity of breadth-first search (BFS)?

Answer: $O(V + E)$. Explores all vertices and their adjacent edges.

Flashcard 47: Identify the Big O notation for the average case of bubble sort.

Answer: $O(n^2)$. Adjacent swaps still require quadratic comparisons.

Flashcard 48: Find and correct the error: 'The time complexity of merge sort is $O(n^2)$.'

Answer: Correct: 'The time complexity of merge sort is $O(n \text{ log } n)$.'. Merge sort consistently divides and merges efficiently.

Flashcard 49: State the Big O notation for a linear search algorithm.

Answer: $O(n)$. Examines each element sequentially until found.

Flashcard 50: What is the average case time complexity of quicksort?

Answer: $O(n \text{ log } n)$. Balanced partitioning creates optimal divide-and-conquer.

Flashcard 51: State the time complexity of selection sort.

Answer: $O(n^2)$. Nested loops to find minimum and swap elements.

Flashcard 52: State the Big O notation for a depth-first search (DFS) space complexity.

Answer: $O(V)$. Recursion stack depth limited by vertex count.

Flashcard 53: Identify the time complexity of a hash table search operation.

Answer: $O(1)$. Direct access through hash function calculation.

Flashcard 54: Identify the Big O notation for the average case of bubble sort.

Answer: $O(n^2)$. Adjacent swaps still require quadratic comparisons.

Flashcard 55: What is the time complexity of breadth-first search (BFS)?

Answer: $O(V + E)$. Explores all vertices and their adjacent edges.

Flashcard 56: What does the term 'polynomial time' mean in algorithmic complexity?

Answer: It means time complexity is $O(n^k)$ for constant $k$. Runtime bounded by polynomial function of input size.

Flashcard 57: Find and correct the error: 'A binary search has $O(n)$ complexity.'

Answer: Correct: 'A binary search has $O(\text{log } n)$ complexity.'. Binary search divides search space logarithmically.

Flashcard 58: Identify the time complexity of Prim's algorithm using a priority queue.

Answer: $O(E \text{ log } V)$. Priority queue operations dominate edge processing time.

Flashcard 59: What is the definition of algorithmic efficiency?

Answer: Algorithmic efficiency measures resource usage. Focuses on time and space usage as performance metrics.

Flashcard 60: Which algorithm has a time complexity of $O(n)$?

Answer: Linear search algorithm. Checks each element once in worst case.

Flashcard 61: Identify the time complexity of Prim's algorithm using a priority queue.

Answer: $O(E \text{ log } V)$. Priority queue operations dominate edge processing time.

Flashcard 62: What is the worst-case time complexity of insertion sort?

Answer: $O(n^2)$. Comparisons increase quadratically for reverse-sorted input.

Flashcard 63: Find and correct the error: 'BFS has a space complexity of $O(E)$.'

Answer: Correct: 'BFS has a space complexity of $O(V)$.'. Queue stores vertices, not edges during traversal.

Flashcard 64: What is the Big O notation for an algorithm with logarithmic time complexity?

Answer: $O(\text{log } n)$. Search space halves with each comparison step.

Flashcard 65: What is the time complexity of a merge sort algorithm?

Answer: $O(n \text{ log } n)$. Divide-and-conquer with linear merge operations.

Flashcard 66: Identify the time complexity of the Bellman-Ford algorithm.

Answer: $O(VE)$. Relaxes edges multiple times across all vertices.

Flashcard 67: State the Big O notation for a linear search algorithm.

Answer: $O(n)$. Examines each element sequentially until found.

Flashcard 68: Identify the Big O notation for the best case of quicksort.

Answer: $O(n \text{ log } n)$. Good pivot creates balanced recursive partitions.

Flashcard 69: What is the space complexity of breadth-first search (BFS)?

Answer: $O(V)$. Queue size bounded by number of vertices.

Flashcard 70: What is the space complexity of a recursive algorithm using stack?

Answer: $O(n)$. Call stack grows proportionally with recursion depth.

Flashcard 71: State the Big O notation for the worst case of quicksort.

Answer: $O(n^2)$. Poor pivot selection leads to unbalanced partitions.

Flashcard 72: What is the time complexity of Dijkstra's algorithm?

Answer: $O(V^2)$. Uses adjacency matrix for dense graph representation.

Flashcard 73: What is the time complexity of the Floyd-Warshall algorithm?

Answer: $O(n^3)$. All-pairs shortest path with triple nested loops.

Flashcard 74: Find the time complexity of the worst case of bubble sort.

Answer: $O(n^2)$. Compares adjacent pairs through nested iterations.

Flashcard 75: Find and correct the error: 'BFS has a space complexity of $O(E)$.'

Answer: Correct: 'BFS has a space complexity of $O(V)$.'. Queue stores vertices, not edges during traversal.

Flashcard 76: Identify the time complexity for depth-first search (DFS).

Answer: $O(V + E)$. Visits each vertex and edge exactly once.

Flashcard 77: What is the space complexity of a recursive algorithm using stack?

Answer: $O(n)$. Call stack grows proportionally with recursion depth.

Flashcard 78: State the Big O notation for an exponential time algorithm.

Answer: $O(2^n)$. Runtime doubles with each additional input element.