Data Structures u0026 Algorithms: Complexity Analysis Essentials Quiz

This challenging quiz evaluates your understanding of foundational data structures, algorithmic complexity notations, and the nuances of time and space complexity analysis. Tackle scenario-based questions to demonstrate mastery of Big O, Big Θ, and Big Ω.

1. 1. Best, Worst, and Average Case Complexity

   Which of the following statements correctly distinguishes between Big O, Big Θ, and Big Ω notations regarding the time complexity of an algorithm?

   1. Big O gives an average bound, Big Ω gives an upper bound, Big Θ gives a lower bound.
   2. Big O gives the best case, Big Ω gives the worst case, Big Θ gives the average case.
   3. Big O gives an upper bound, Big Ω gives a lower bound, Big Θ gives a tight bound.
   4. Big O gives a tight bound, Big Ω gives an upper bound, Big Θ gives a lower bound.
   5. Big O gives a probabilistic bound, Big Ω and Big Θ give exact bounds.

2. 2. Nested Loops Complexity

   Given the code fragment: for(i = 0; i u003C n; i++) { for(j = 0; j u003C n; j++) { /* constant time */ } }, what is the Big O time complexity in terms of n?

   1. O(logn^2)
   2. O(2n)
   3. O(nlogn)
   4. O(n)
   5. O(n^2)

3. 3. Space Complexity of Recursive Algorithms

   For a recursive function that calls itself once per invocation until n equals 0 (e.g., computing factorial recursively), what is the space complexity with respect to n, excluding input size?

   1. O(n!)
   2. O(n)
   3. O(logn)
   4. O(n^2)
   5. O(1)

4. 4. Amortized Analysis Interpretation

   When analyzing a dynamic array that doubles its capacity upon reaching its limit, what is the amortized time complexity of inserting n elements?

   1. O(1/n)
   2. O(1)
   3. O(nlogn)
   4. O(logn)
   5. O(n)

5. 5. Lower Bound for Comparison Sorting

   What is the asymptotic lower bound for the number of comparisons needed to sort n distinct numbers using any comparison-based sorting algorithm?

   1. Ω(logn)
   2. Ω(n^2)
   3. Ω(nlogn)
   4. Ω(n)
   5. Ω(n!)

6. 6. Worst-Case Complexity of Linear Search

   Given a linear search on an unsorted array of n elements, what is the worst-case time complexity?

   1. O(1)
   2. O(n^2)
   3. O(n)
   4. O(nlogn)
   5. O(logn)

7. 7. Average Case Analysis in Hashing

   Assuming a good hash function and a hashtable of size proportional to n, what is the average-case time complexity for search operations?

   1. O(n)
   2. O(logn)
   3. O(nlogn)
   4. O(1)
   5. O(n^2)

8. 8. Tightest Bound for Binary Search

   Which of the following notations gives the tightest bound for the time complexity of binary search on a sorted array of n elements?

   1. Θ(n^2)
   2. O(1)
   3. Θ(logn)
   4. Ω(n)
   5. O(n)

9. 9. Space Complexity of Adjacency Matrix for Sparse Graph

   What is the space complexity of representing a sparse graph with n vertices and e edges using an adjacency matrix?

   1. O(nlogn)
   2. O(n+e)
   3. O(e)
   4. O(n^2)
   5. O(n)

10. 10. Effect of Ignoring Constants and Lower Order Terms

    Given an algorithm with time complexity 3n^2 + 4n + 5, what is its Big O classification?

    1. O(logn)
    2. O(n^4)
    3. O(n)
    4. O(nlogn)
    5. O(n^2)