Informal Run-Time Analysis - AP Computer Science A

1. Identify the Big O for the best-case of insertion sort.

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

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

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

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

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

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

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

5. State the Big O notation for heap sort.

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

6. State the Big O for matrix multiplication of two $n \times n$ matrices.

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

7. What is the Big O for calculating the power of a number using divide and conquer?

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

8. Which Big O notation is typical for a nested loop with two variables?

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

9. What is the Big O for finding the maximum element in an unsorted array?

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

10. What is the Big O for reversing a string of length $n$?

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

11. Identify the Big O for the worst-case of merge sort.

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

12. What does Big O notation describe?

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

13. Identify the Big O for appending an element to a dynamic array.

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

14. Which Big O notation represents constant time complexity?

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

15. Identify the Big O notation for the Fibonacci sequence using iteration.

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

16. What is the Big O notation for accessing an element in an array?

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

17. Find the Big O for the average case of searching in a hash table.

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

18. What is the Big O for removing an element from a queue?

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

19. What is the Big O for traversing all elements in a binary tree?

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

20. What is the Big O for deleting an element from a linked list?

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

21. State the Big O for calculating the factorial of a number using recursion.

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

22. State the time complexity for adding an element to a stack.

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

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

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

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

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

25. What is the Big O for finding the minimum element in an unsorted array?

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

26. What is the Big O of quicksort in the best case?

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

27. Find the Big O for the worst-case scenario of quicksort.

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

28. What is the Big O for finding an element in an unsorted linked list?

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

29. State the Big O notation for bubble sort in the average case.

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

30. State the Big O notation of merge sort.

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

31. State the Big O notation for the best-case scenario of quicksort.

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

32. Identify the Big O for accessing an element in a hash table in the average case.

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

33. Identify the Big O notation for a loop that halves the input size each iteration.

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

34. What is the Big O for checking if a number is prime using trial division?

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

35. State the Big O for removing the smallest element from a priority queue.

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

36. Identify the Big O for searching in a balanced binary search tree.

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

37. Find the Big O for the worst-case of searching in a hash table.

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

38. State the Big O for adding an element to a binary heap.

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

Study these flashcards