Algorithmic Efficiency - AP Computer Science Principles

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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