Algorithms and Data Structures

The Observer Pattern provides multiple benefits: it creates abstract coupling between subjects and observers (they know each other only through interfaces), allows them to exist at different abstraction layers (UI layer can observe business layer), and supports broadcast-style notifications where one change notifies multiple observers simultaneously. Option A correctly identifies abstract coupling, which is a genuine benefit. Option B correctly states subjects and observers can be at different abstraction layers (e.g., business logic notifying UI components). Option C correctly identifies broadcast notification support. Therefore, option D (All of the above) is the correct choice.

The Strategy Pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. The context object delegates work to a strategy object, and at runtime, only one strategy instance is active and being used. This allows the algorithm to vary independently from clients that use it. Option A correctly identifies that only one strategy is active at a time, the selected strategy. Option B incorrectly suggests the pattern encapsulates classes with different functionalities (it encapsulates interchangeable algorithms for the same task). Option C incorrectly imposes a naming constraint that isn't part of the pattern. Option D is incorrect since option A is valid.

Binary search works by repeatedly dividing the search interval in half, eliminating half of the remaining elements each time. This logarithmic reduction means time complexity is O(log n), making it much faster than linear O(n) search for sorted data.

A side effect occurs when a function or module modifies state outside its local scope, such as changing a global variable or modifying data passed by reference. This makes code harder to reason about and test, since the effects aren't contained within the module itself.

Both arrays and linked lists store elements in a sequential manner where each element has a clear 'next' relationship, making them linear data structures. The only non-linear data structures among common types are trees and graphs, which aren't listed here.

Arrays store elements sequentially in contiguous memory locations, where each element can be accessed directly by its index. This linear organization distinguishes them from non-linear structures like trees and graphs, where elements have multiple connections and hierarchical relationships.

Traversal is the process of systematically visiting each element in a data structure exactly once, typically to perform some operation on each element. Unlike searching (which looks for specific values) or sorting (which rearranges elements), traversal focuses on complete, sequential access.

Search is the operation of locating a specific element with a given value within a data structure. While traversal visits every element, search focuses on finding particular targets, using algorithms like linear search or binary search to efficiently locate the desired value.

Arrays have a fixed size determined at creation, making them ideal for relatively permanent collections where the number of elements doesn't change frequently. Their contiguous memory allocation provides efficient random access, but resizing requires copying all elements to a new array.

Linked lists use dynamic memory allocation where each node contains data and a pointer to the next node, making them ideal for collections with frequent size changes. Adding or removing elements only requires updating pointers, making these operations O(1) at known positions.

Array declarations require the array's name, data type, and index set (bounds), but do not require specifying the actual data values. The first element's value is set later through assignment or initialization, not as part of the declaration itself.

Array elements are stored in consecutive memory locations, enabling efficient address calculation. By knowing the base address (first element's location) and element size, the computer can directly compute any element's address using simple arithmetic: base_address + (index × element_size).

Algorithm efficiency is measured by time complexity (how execution time grows with input size) and space complexity (how memory usage grows with input size). These two metrics provide a complete picture of an algorithm's resource consumption and performance characteristics.

Complexity theory analyzes algorithms through three standard cases: best case (optimal performance), worst case (poorest performance), and average case (expected performance). 'Null case' is not a standard concept in complexity analysis and doesn't represent a meaningful scenario.

The average case occurs when the item is found somewhere in the middle, requiring approximately n/2 comparisons on average. The worst case occurs when the item is the last element or not present at all, requiring all n comparisons.

Average case complexity is more complicated to analyze than worst case because it requires knowledge about the probability distribution of all possible inputs. Worst case analysis only needs to find the maximum runtime over all inputs.

In a linear search, the algorithm checks each element sequentially from the beginning. The worst-case scenario occurs when the target item is at the very end of the array or not present at all, requiring a full traversal of the entire array.

Linear search has O(n) time complexity because in the worst case it must examine each of the n elements once. The runtime grows linearly with the input size.

Bubble sort has O(n²) time complexity because it uses nested loops - the outer loop runs n times and the inner loop runs up to n times in the worst case, giving n×n = n² comparisons.