Algorithmic Efficiency - AP Computer Science Principles

1. What is the time complexity of heap sort?

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

2. What is the Big O notation for an algorithm with constant time?

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

3. Identify the time complexity of Kruskal's algorithm.

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

4. Find the time complexity of the worst case of bubble sort.

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

5. State the time complexity of selection sort.

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

6. Identify the Big O notation for matrix multiplication.

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

7. Identify the Big O notation for a bubble sort algorithm.

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

8. State the Big O notation for a binary search algorithm.

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

9. Identify the time complexity for depth-first search (DFS).

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

10. What is the time complexity of a naive string matching algorithm?

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

11. What is the Big O notation for an algorithm with logarithmic time complexity?

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

12. State the Big O notation for searching an unsorted list.

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

13. Identify the Big O notation for the best case of quicksort.

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

14. What is the space complexity of an algorithm?

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

15. What does Big O notation describe?

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

16. What is the time complexity of a merge sort algorithm?

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

17. Which algorithm has a time complexity of $O(n)$?

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

18. What is the Big O notation for Fibonacci sequence using recursion?

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

19. Identify the Big O notation for insertion sort in the best case.

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

20. What is the time complexity of the Floyd-Warshall algorithm?

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

21. What is the time complexity of breadth-first search (BFS)?

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

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

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

23. What is the average case time complexity of quicksort?

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

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

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

25. Identify the time complexity of a hash table search operation.

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

26. Identify the Big O notation for the average case of bubble sort.

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

27. What does the term 'polynomial time' mean in algorithmic complexity?

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

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

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

29. What is the definition of algorithmic efficiency?

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

30. Identify the time complexity of Prim's algorithm using a priority queue.

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

31. What is the worst-case time complexity of insertion sort?

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

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

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

33. Identify the time complexity of the Bellman-Ford algorithm.

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

34. State the Big O notation for a linear search algorithm.

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

35. What is the space complexity of breadth-first search (BFS)?

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

36. State the Big O notation for the worst case of quicksort.

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

37. What is the time complexity of Dijkstra's algorithm?

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

38. What is the space complexity of a recursive algorithm using stack?

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

39. State the Big O notation for an exponential time algorithm.

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

Study these flashcards