Informal Run-Time Analysis - AP Computer Science A
Card 1 of 30
What is the Big O for finding an element in an unsorted linked list?
What is the Big O for finding an element in an unsorted linked list?
Tap to reveal answer
$O(n)$. Must traverse list sequentially to find element.
$O(n)$. Must traverse list sequentially to find element.
← Didn't Know|Knew It →
State the Big O notation for a linear search algorithm.
State the Big O notation for a linear search algorithm.
Tap to reveal answer
$O(n)$. Must check each element sequentially in worst case.
$O(n)$. Must check each element sequentially in worst case.
← Didn't Know|Knew It →
Identify the Big O for binary search in a sorted array.
Identify the Big O for binary search in a sorted array.
Tap to reveal answer
$O(\text{log } n)$. Eliminates half the search space each comparison.
$O(\text{log } n)$. Eliminates half the search space each comparison.
← Didn't Know|Knew It →
Which Big O notation represents constant time complexity?
Which Big O notation represents constant time complexity?
Tap to reveal answer
$O(1)$. Execution time stays the same regardless of input size.
$O(1)$. Execution time stays the same regardless of input size.
← Didn't Know|Knew It →
State the Big O notation for bubble sort in the average case.
State the Big O notation for bubble sort in the average case.
Tap to reveal answer
$O(n^2)$. Nested loops compare each element with every other element.
$O(n^2)$. Nested loops compare each element with every other element.
← Didn't Know|Knew It →
What is the Big O of quicksort in the best case?
What is the Big O of quicksort in the best case?
Tap to reveal answer
$O(n \text{ log } n)$. Efficiently partitions and divides the problem size.
$O(n \text{ log } n)$. Efficiently partitions and divides the problem size.
← Didn't Know|Knew It →
Find the Big O for the worst-case scenario of quicksort.
Find the Big O for the worst-case scenario of quicksort.
Tap to reveal answer
$O(n^2)$. Poor pivot choice leads to unbalanced partitions.
$O(n^2)$. Poor pivot choice leads to unbalanced partitions.
← Didn't Know|Knew It →
State the Big O notation of merge sort.
State the Big O notation of merge sort.
Tap to reveal answer
$O(n \text{ log } n)$. Always divides array in half regardless of input.
$O(n \text{ log } n)$. Always divides array in half regardless of input.
← Didn't Know|Knew It →
Identify the Big O for searching in a balanced binary search tree.
Identify the Big O for searching in a balanced binary search tree.
Tap to reveal answer
$O(\text{log } n)$. Tree height is logarithmic when properly balanced.
$O(\text{log } n)$. Tree height is logarithmic when properly balanced.
← Didn't Know|Knew It →
What is the Big O notation for accessing an element in an array?
What is the Big O notation for accessing an element in an array?
Tap to reveal answer
$O(1)$. Direct index access using memory addresses.
$O(1)$. Direct index access using memory addresses.
← Didn't Know|Knew It →
State the time complexity for adding an element to a stack.
State the time complexity for adding an element to a stack.
Tap to reveal answer
$O(1)$. Simple operation at the top of the stack.
$O(1)$. Simple operation at the top of the stack.
← Didn't Know|Knew It →
What is the Big O for removing an element from a queue?
What is the Big O for removing an element from a queue?
Tap to reveal answer
$O(1)$. Direct access to front element in queue structure.
$O(1)$. Direct access to front element in queue structure.
← Didn't Know|Knew It →
Find the Big O for the worst-case of searching in a hash table.
Find the Big O for the worst-case of searching in a hash table.
Tap to reveal answer
$O(n)$. All elements may hash to same bucket requiring linear search.
$O(n)$. All elements may hash to same bucket requiring linear search.
← Didn't Know|Knew It →
State the Big O notation for the best-case scenario of quicksort.
State the Big O notation for the best-case scenario of quicksort.
Tap to reveal answer
$O(n \text{ log } n)$. Efficiently partitions and divides the problem size.
$O(n \text{ log } n)$. Efficiently partitions and divides the problem size.
← Didn't Know|Knew It →
Identify the Big O for the worst-case of merge sort.
Identify the Big O for the worst-case of merge sort.
Tap to reveal answer
$O(n \text{ log } n)$. Always divides array in half regardless of input.
$O(n \text{ log } n)$. Always divides array in half regardless of input.
← Didn't Know|Knew It →
What is the Big O for deleting an element from a linked list?
What is the Big O for deleting an element from a linked list?
Tap to reveal answer
$O(n)$. Must traverse list to find element before deletion.
$O(n)$. Must traverse list to find element before deletion.
← Didn't Know|Knew It →
State the Big O notation for heap sort.
State the Big O notation for heap sort.
Tap to reveal answer
$O(n \text{ log } n)$. Maintains heap property with logarithmic operations.
$O(n \text{ log } n)$. Maintains heap property with logarithmic operations.
← Didn't Know|Knew It →
Identify the Big O for the best-case of insertion sort.
Identify the Big O for the best-case of insertion sort.
Tap to reveal answer
$O(n)$. Array is already sorted requiring minimal operations.
$O(n)$. Array is already sorted requiring minimal operations.
← Didn't Know|Knew It →
What is the Big O for traversing all elements in a binary tree?
What is the Big O for traversing all elements in a binary tree?
Tap to reveal answer
$O(n)$. Must visit each node exactly once.
$O(n)$. Must visit each node exactly once.
← Didn't Know|Knew It →
State the Big O for adding an element to a binary heap.
State the Big O for adding an element to a binary heap.
Tap to reveal answer
$O(\text{log } n)$. Maintains heap property by bubbling up.
$O(\text{log } n)$. Maintains heap property by bubbling up.
← Didn't Know|Knew It →
Which Big O notation is typical for a nested loop with two variables?
Which Big O notation is typical for a nested loop with two variables?
Tap to reveal answer
$O(n^2)$. Each element compared with every other element.
$O(n^2)$. Each element compared with every other element.
← Didn't Know|Knew It →
Identify the Big O notation for a loop that halves the input size each iteration.
Identify the Big O notation for a loop that halves the input size each iteration.
Tap to reveal answer
$O(\text{log } n)$. Input size reduces by half each iteration.
$O(\text{log } n)$. Input size reduces by half each iteration.
← Didn't Know|Knew It →
What is the Big O for finding the minimum element in an unsorted array?
What is the Big O for finding the minimum element in an unsorted array?
Tap to reveal answer
$O(n)$. Must examine every element to find minimum.
$O(n)$. Must examine every element to find minimum.
← Didn't Know|Knew It →
State the Big O for removing the smallest element from a priority queue.
State the Big O for removing the smallest element from a priority queue.
Tap to reveal answer
$O(\text{log } n)$. Heap maintains order with logarithmic height.
$O(\text{log } n)$. Heap maintains order with logarithmic height.
← Didn't Know|Knew It →
Find the Big O for the average case of searching in a hash table.
Find the Big O for the average case of searching in a hash table.
Tap to reveal answer
$O(1)$. Good hash function distributes elements evenly.
$O(1)$. Good hash function distributes elements evenly.
← Didn't Know|Knew It →
Identify the Big O notation for the Fibonacci sequence using iteration.
Identify the Big O notation for the Fibonacci sequence using iteration.
Tap to reveal answer
$O(n)$. Single loop calculates each term once.
$O(n)$. Single loop calculates each term once.
← Didn't Know|Knew It →
What is the Big O for reversing a string of length $n$?
What is the Big O for reversing a string of length $n$?
Tap to reveal answer
$O(n)$. Must process each character exactly once.
$O(n)$. Must process each character exactly once.
← Didn't Know|Knew It →
State the Big O for matrix multiplication of two $n \times n$ matrices.
State the Big O for matrix multiplication of two $n \times n$ matrices.
Tap to reveal answer
$O(n^3)$. Three nested loops for standard algorithm.
$O(n^3)$. Three nested loops for standard algorithm.
← Didn't Know|Knew It →
What is the Big O for finding the maximum element in an unsorted array?
What is the Big O for finding the maximum element in an unsorted array?
Tap to reveal answer
$O(n)$. Must examine every element to find maximum.
$O(n)$. Must examine every element to find maximum.
← Didn't Know|Knew It →
Identify the Big O for appending an element to a dynamic array.
Identify the Big O for appending an element to a dynamic array.
Tap to reveal answer
$O(1)$. Amortized constant time for most operations.
$O(1)$. Amortized constant time for most operations.
← Didn't Know|Knew It →