AP Computer Science a Flashcards: Informal Run Time Analysis

What this deck covers

This deck focuses on Informal Run Time Analysis, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science a.

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 for the best-case of insertion sort.

Answer: $O(n)$. Array is already sorted requiring minimal operations.

Flashcard 2: Identify the Big O for binary search in a sorted array.

Answer: $O(\text{log } n)$. Eliminates half the search space each comparison.

Flashcard 3: Find the Big O for sorting a linked list using merge sort.

Answer: $O(n \text{ log } n)$. Divide and conquer maintains efficient time complexity.

Flashcard 4: Identify the Big O for sorting algorithms based on comparisons in the general case.

Answer: $O(n \text{ log } n)$. Theoretical lower bound for comparison-based sorting.

Flashcard 5: Identify the Big O notation for the Fibonacci sequence using iteration.

Answer: $O(n)$. Single loop calculates each term once.

Flashcard 6: State the Big O notation for heap sort.

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

Flashcard 7: Identify the Big O for the worst-case of merge sort.

Answer: $O(n \text{ log } n)$. Always divides array in half regardless of input.

Flashcard 8: State the Big O for matrix multiplication of two $n \times n$ matrices.

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

Flashcard 9: What is the Big O for calculating the power of a number using divide and conquer?

Answer: $O(\text{log } n)$. Exponentiation by squaring reduces problem size.

Flashcard 10: Which Big O notation is typical for a nested loop with two variables?

Answer: $O(n^2)$. Each element compared with every other element.

Flashcard 11: Identify the Big O for binary search in a sorted array.

Answer: $O(\text{log } n)$. Eliminates half the search space each comparison.

Flashcard 12: What is the Big O for finding the maximum element in an unsorted array?

Answer: $O(n)$. Must examine every element to find maximum.

Flashcard 13: What is the Big O for reversing a string of length $n$?

Answer: $O(n)$. Must process each character exactly once.

Flashcard 14: State the Big O notation for heap sort.

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

Flashcard 15: Identify the Big O for the worst-case of merge sort.

Answer: $O(n \text{ log } n)$. Always divides array in half regardless of input.

Flashcard 16: What is the Big O for finding the maximum element in an unsorted array?

Answer: $O(n)$. Must examine every element to find maximum.

Flashcard 17: State the Big O for removing the smallest element from a priority queue.

Answer: $O(\text{log } n)$. Heap maintains order with logarithmic height.

Flashcard 18: Identify the Big O for appending an element to a dynamic array.

Answer: $O(1)$. Amortized constant time for most operations.

Flashcard 19: What does Big O notation describe?

Answer: Big O describes the upper bound of an algorithm's run-time complexity. It measures how execution time grows with input size.

Flashcard 20: Identify the Big O for appending an element to a dynamic array.

Answer: $O(1)$. Amortized constant time for most operations.

Flashcard 21: Which Big O notation represents constant time complexity?

Answer: $O(1)$. Execution time stays the same regardless of input size.

Flashcard 22: Identify the Big O notation for the Fibonacci sequence using iteration.

Answer: $O(n)$. Single loop calculates each term once.

Flashcard 23: State the Big O for adding an element to a binary heap.

Answer: $O(\text{log } n)$. Maintains heap property by bubbling up.

Flashcard 24: State the Big O for computing the greatest common divisor using Euclid's algorithm.

Answer: $O(\text{log } n)$. Repeatedly divides numbers by their remainder.

Flashcard 25: What is the Big O notation for accessing an element in an array?

Answer: $O(1)$. Direct index access using memory addresses.

Flashcard 26: State the time complexity for adding an element to a stack.

Answer: $O(1)$. Simple operation at the top of the stack.

Flashcard 27: Find the Big O for sorting a linked list using merge sort.

Answer: $O(n \text{ log } n)$. Divide and conquer maintains efficient time complexity.

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

Answer: $O(n)$. Must check each element sequentially in worst case.

Flashcard 29: State the Big O notation of merge sort.

Answer: $O(n \text{ log } n)$. Always divides array in half regardless of input.

Flashcard 30: Identify the Big O for sorting algorithms based on comparisons in the general case.

Answer: $O(n \text{ log } n)$. Theoretical lower bound for comparison-based sorting.

Flashcard 31: Find the Big O for the average case of searching in a hash table.

Answer: $O(1)$. Good hash function distributes elements evenly.

Flashcard 32: What is the Big O for finding an element in an unsorted linked list?

Answer: $O(n)$. Must traverse list sequentially to find element.

Flashcard 33: What is the Big O notation for accessing an element in an array?

Answer: $O(1)$. Direct index access using memory addresses.

Flashcard 34: What is the Big O of quicksort in the best case?

Answer: $O(n \text{ log } n)$. Efficiently partitions and divides the problem size.

Flashcard 35: What is the Big O for removing an element from a queue?

Answer: $O(1)$. Direct access to front element in queue structure.

Flashcard 36: What is the Big O for traversing all elements in a binary tree?

Answer: $O(n)$. Must visit each node exactly once.

Flashcard 37: What is the Big O for deleting an element from a linked list?

Answer: $O(n)$. Must traverse list to find element before deletion.

Flashcard 38: State the Big O for calculating the factorial of a number using recursion.

Answer: $O(n)$. Makes one recursive call for each number.

Flashcard 39: Which Big O notation represents constant time complexity?

Answer: $O(1)$. Execution time stays the same regardless of input size.

Flashcard 40: State the time complexity for adding an element to a stack.

Answer: $O(1)$. Simple operation at the top of the stack.

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

Answer: $O(n)$. Must check each element sequentially in worst case.

Flashcard 42: What is the Big O for traversing all elements in a binary tree?

Answer: $O(n)$. Must visit each node exactly once.

Flashcard 43: State the Big O for computing the greatest common divisor using Euclid's algorithm.

Answer: $O(\text{log } n)$. Repeatedly divides numbers by their remainder.

Flashcard 44: State the Big O notation for the best-case scenario of quicksort.

Answer: $O(n \text{ log } n)$. Efficiently partitions and divides the problem size.

Flashcard 45: What is the Big O for finding the minimum element in an unsorted array?

Answer: $O(n)$. Must examine every element to find minimum.

Flashcard 46: What is the Big O of quicksort in the best case?

Answer: $O(n \text{ log } n)$. Efficiently partitions and divides the problem size.

Flashcard 47: Which Big O notation is typical for a nested loop with two variables?

Answer: $O(n^2)$. Each element compared with every other element.

Flashcard 48: Identify the Big O for the best-case of insertion sort.

Answer: $O(n)$. Array is already sorted requiring minimal operations.

Flashcard 49: Find the Big O for the worst-case scenario of quicksort.

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

Flashcard 50: State the Big O for calculating the factorial of a number using recursion.

Answer: $O(n)$. Makes one recursive call for each number.

Flashcard 51: What is the Big O for deleting an element from a linked list?

Answer: $O(n)$. Must traverse list to find element before deletion.

Flashcard 52: Identify the Big O for searching in a balanced binary search tree.

Answer: $O(\text{log } n)$. Tree height is logarithmic when properly balanced.

Flashcard 53: What is the Big O for finding an element in an unsorted linked list?

Answer: $O(n)$. Must traverse list sequentially to find element.

Flashcard 54: What is the Big O for removing an element from a queue?

Answer: $O(1)$. Direct access to front element in queue structure.

Flashcard 55: Find the Big O for the worst-case of searching in a hash table.

Answer: $O(n)$. All elements may hash to same bucket requiring linear search.

Flashcard 56: Identify the Big O notation for a loop that halves the input size each iteration.

Answer: $O(\text{log } n)$. Input size reduces by half each iteration.

Flashcard 57: Identify the Big O for accessing an element in a hash table in the average case.

Answer: $O(1)$. Good hash function provides direct element access.

Flashcard 58: State the Big O notation for bubble sort in the average case.

Answer: $O(n^2)$. Nested loops compare each element with every other element.

Flashcard 59: State the Big O notation of merge sort.

Answer: $O(n \text{ log } n)$. Always divides array in half regardless of input.

Flashcard 60: State the Big O notation for the best-case scenario of quicksort.

Answer: $O(n \text{ log } n)$. Efficiently partitions and divides the problem size.

Flashcard 61: State the Big O notation for bubble sort in the average case.

Answer: $O(n^2)$. Nested loops compare each element with every other element.

Flashcard 62: Identify the Big O for accessing an element in a hash table in the average case.

Answer: $O(1)$. Good hash function provides direct element access.

Flashcard 63: What does Big O notation describe?

Answer: Big O describes the upper bound of an algorithm's run-time complexity. It measures how execution time grows with input size.

Flashcard 64: Find the Big O for the worst-case scenario of quicksort.

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

Flashcard 65: What is the Big O for finding the minimum element in an unsorted array?

Answer: $O(n)$. Must examine every element to find minimum.

Flashcard 66: Identify the Big O notation for a loop that halves the input size each iteration.

Answer: $O(\text{log } n)$. Input size reduces by half each iteration.

Flashcard 67: What is the Big O for checking if a number is prime using trial division?

Answer: $O(\text{sqrt } n)$. Only test divisors up to square root.

Flashcard 68: State the Big O for matrix multiplication of two $n \times n$ matrices.

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

Flashcard 69: State the Big O for removing the smallest element from a priority queue.

Answer: $O(\text{log } n)$. Heap maintains order with logarithmic height.

Flashcard 70: Find the Big O for the average case of searching in a hash table.

Answer: $O(1)$. Good hash function distributes elements evenly.

Flashcard 71: Identify the Big O for searching in a balanced binary search tree.

Answer: $O(\text{log } n)$. Tree height is logarithmic when properly balanced.

Flashcard 72: Find the Big O for the worst-case of searching in a hash table.

Answer: $O(n)$. All elements may hash to same bucket requiring linear search.

Flashcard 73: What is the Big O for checking if a number is prime using trial division?

Answer: $O(\sqrt{n})$. Only test divisors up to square root.

Flashcard 74: What is the Big O for reversing a string of length $n$?

Answer: $O(n)$. Must process each character exactly once.

Flashcard 75: State the Big O for adding an element to a binary heap.

Answer: $O(\text{log } n)$. Maintains heap property by bubbling up.

Flashcard 76: What is the Big O for calculating the power of a number using divide and conquer?

Answer: $O(\text{log } n)$. Exponentiation by squaring reduces problem size.