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: What is the time complexity of a merge sort algorithm?

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

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

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

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

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

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

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

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

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

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

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

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

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

Flashcard 8: State the time complexity of selection sort.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Flashcard 16: 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 17: What is the time complexity of Dijkstra's algorithm?

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

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

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

Flashcard 19: 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 20: Identify the time complexity of Kruskal’s algorithm.

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

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

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

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

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

Flashcard 23: 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 24: Identify the Big O notation for the average case of bubble sort.

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

Flashcard 25: 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 26: State the Big O notation for searching an unsorted list.

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

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

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

Flashcard 28: 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 29: State the Big O notation for a linear search algorithm.

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

Flashcard 30: 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.