Big-O Complexity in Game Entity Updates and Collision Detection Quiz

This quiz explores computational complexities related to entity updates and collision checks in games, emphasizing time and space trade-offs in practical scenarios.

1. Understanding Linear Time in Entity Updates

   What is the Big-O time complexity for updating the position of each entity when you have 'n' entities in a game loop?

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n log n)
   5. O(n^2)

2. Naive Collision Checks

   If you check for collisions between every pair of entities in a list of 'n' entities, what is the time complexity in Big-O notation?

   1. O(2n)
   2. O(n^3)
   3. O(log n)
   4. O(n)
   5. O(n^2)

3. Optimizing with Grid Partitioning

   When using a spatial grid to reduce collision checks in a 2D game, which time complexity does collision checking per entity approach in the best-case scenario?

   1. O(log n)
   2. O(1)
   3. O(n log n)
   4. O(n)
   5. O(n^2)

4. Space Complexity of Entity Lists

   What is the space complexity of storing properties (like position and velocity) for 'n' entities, each having a fixed number of properties?

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n^2)
   5. O(n log n)

5. Broad Phase Collision Detection

   Which Big-O complexity best describes the time to sort entities along one axis as a first step in sweep-and-prune collision detection?

   1. O(n log n)
   2. O(1)
   3. O(log n)
   4. O(n)
   5. O(n^2)

6. Spatial Hashing Lookup

   If you store entity positions in a hash map by grid cell, what is the average-case time complexity to retrieve all entities in a specific cell?

   1. O(log n)
   2. O(n^2)
   3. O(1)
   4. O(n)
   5. O(n log n)

7. Quadtree Subdivision

   In a balanced quadtree used for 2D spatial partitioning, what is the average time complexity for inserting an entity?

   1. O(log n)
   2. O(1)
   3. O(n)
   4. O(n log n)
   5. O(n^2)

8. Memory Usage with Quadtrees

   What is the typical space complexity for storing ‘n’ entities in a quadtree structure?

   1. O(1)
   2. O(n^2)
   3. O(n)
   4. O(n log n)
   5. O(log n)

9. Constant-Time Updates

   Which of the following tasks has O(1) time complexity per entity in a typical game update loop?

   1. Building a quadtree from scratch
   2. Checking every pair of entities for collisions
   3. Sorting all entities by their x-coordinate
   4. Updating the health of an entity
   5. Searching a linked list for a value

10. Space-Time Trade-offs

    Which method would use more space to gain faster collision checks in a large game world?

    1. Linear searching without any auxiliary data
    2. Ignoring entity positions
    3. Using a simple array for all entities
    4. Checking all pairs without any partitioning
    5. Using a grid-based spatial partitioning