Big-O of Common Data Structures: Arrays, Stacks, Queues, and Linked Lists Quiz

Enhance your understanding of time complexities for common data structures, including arrays, stacks, queues, and linked lists. This quiz focuses on analyzing and comparing Big-O performance for various operations, helping you grasp efficient algorithm design.

1. Access Time in Arrays

   What is the Big-O time complexity for accessing an element at a specific index in a static array of size n, such as getting the 5th element?

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

   Explanation: Accessing an element by index in a static array takes constant time, or O(1), because the address can be calculated directly. O(n) would mean access time increases with the array size, which is not the case here. O(log n) applies to searches in binary search trees but not direct array indexing. O(n^2) is much higher and relates to nested loops, not array access. Direct access is always O(1) in static arrays.

2. Linked List Searching

   Given an unsorted singly linked list of n nodes, what is the worst-case Big-O time complexity for searching for a value?

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

   Explanation: In a singly linked list, searching for an element requires traversing each node, resulting in O(n) time in the worst case. O(1) is only possible if you know the node's reference in advance. O(log n) is typical for structures that support efficient search like binary search trees, but not for linked lists. O(n log n) is relevant for certain sorting algorithms, not simple searches.

3. Stack Push Operation

   What is the time complexity of pushing an element onto a stack implemented with a linked list or dynamic array?

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

   Explanation: Pushing an element onto a stack takes O(1) time as it involves adding to the top, regardless of how many elements are already present. O(n) or O(n^2) would imply traversing or recalculating many elements, which is not needed here. O(log n) does not apply to stack insertion, as no hierarchical structure is involved. Both linked list and dynamic array stacks support constant-time push operations.

4. Queue Dequeue Complexity

   For a queue implemented with a singly linked list, what is the time complexity of removing (dequeueing) the front element?

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

   Explanation: Removing the front element of a queue implemented with a singly linked list is an O(1) operation, as it only changes the head pointer. O(n) would apply if removal required searching or traversing through the list, but here only a reference is updated. O(log n) and O(n^2) are not relevant, since no sorting or nested operations are needed. Fast dequeuing is a key advantage of this implementation.

5. Insert Operation in Arrays vs Linked Lists

   Which data structure allows for O(1) insertion at the beginning, but has O(n) time for insertion at arbitrary positions?

   1. Queue
   2. Static array
   3. Stack
   4. Singly linked list

   Explanation: A singly linked list can insert elements at the beginning in O(1) time by updating the head pointer, but inserting at arbitrary positions requires traversal, making it O(n). Static arrays require shifting elements for insertions, so they are not O(1) at the beginning. Queues and stacks do not generally allow insertion at arbitrary indices; they follow strict order operations. Thus, singly linked lists combine fast head insertion with slower arbitrary insertion.