Data Structures and Algorithms

This is the classic exponential recurrence. Expanding: T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 4T(n-2) + 3 = 8T(n-3) + 7 = ... = 2^n T(0) + (2^n - 1). The dominant term is 2^n, so T(n) = O(2^n). The n² option would apply to T(n)=T(n-1)+n, and n^log 3 is for divide-and-conquer recurrences.

Kruskal's algorithm uses edge sorting and union-find. Sorting |E| edges takes O(|E| log |E|) ≈ O(|E| log |V|) since |E| ≤ |V|². Union-find operations are nearly O(1) with path compression and union by rank. The dominant cost is sorting, giving O(|E| log |V|). Adjacency list representation is standard.

Prim's algorithm on an adjacency matrix requires scanning all vertices to find the minimum weight edge, taking O(|V|) per vertex. With |V| iterations, total is O(|V|²). With Fibonacci heap + adjacency list, it becomes O(|E| + |V| log |V|), but O(|V|²) is the standard answer for basic implementation.

Prim's algorithm using a binary heap performs O(|E|) extract-min and O(|V|) decrease-key operations, each costing O(log|V|). The dominant term is |E|log|V| because the number of edges is typically greater than vertices. Option B incorrectly writes V as base and E as exponent, while C and D are not the correct complexity for heap-based Prim's.

Using the Master Theorem: T(n) = 2T(n/2) + n^2, we have a=2, b=2, f(n)=n^2. Since n^log_b(a) = n^1 and f(n) = n^2 = Ω(n^(1+ε)) for ε<1, this is Case 3. The regularity condition 2f(n/2) = n^2/2 ≤ cn^2 holds, so T(n) = Θ(n^2). Options B, C, and D do not match this result.

The recurrence T(n) = 2T(√n) + n log n + n requires a different technique. Let m = log n, then T(2^m) = 2T(2^(m/2)) + 2^m * m + 2^m. This recurrence doesn't yield any of the simple forms in options A, B, or C. The complexity involves polynomial-logarithmic terms that don't match the given options, making 'None of these' the correct choice.

Traversal is the process of systematically visiting each element in a data structure exactly once. This fundamental operation is essential for accessing, processing, or analyzing every element in an array, linked list, tree, or other data structure. It forms the basis for many algorithms including searching, sorting, and counting operations.

Both linear search and binary search are fundamental approaches to search operations. Linear search works on unsorted data by checking each element sequentially, while binary search requires sorted data and repeatedly divides the search interval in half, making it much faster for large datasets.

Linear search traverses sequentially through a list to locate a specific item. It examines each element one by one from the beginning until the target is found or the list ends. This simple approach works on any list but is less efficient than binary search for large, sorted datasets.

Insert operation adds a new element to an existing list or data structure. This operation requires placing the new element in the appropriate position while maintaining the structure's properties. In arrays, insertion may require shifting elements, while linked lists can insert efficiently at any position.

Sort operation arranges array elements in a logical order (ascending or descending). This fundamental operation organizes data for efficient searching, analysis, and display. Common sorting algorithms include bubble sort, quick sort, and merge sort, each with different time and space complexity characteristics.

A two-dimensional array is defined as a finite number m × n of homogeneous data elements organized in rows and columns. This structure represents a matrix or table where each element can be accessed using two indices (row and column). It's ideal for representing grids, images, and spreadsheet-like data.

Merge operation combines two similar data structures into a single structure while maintaining order. This operation is fundamental to merge sort algorithms and database operations. In sorted lists, merging creates one sorted list from two sorted lists by comparing elements from both lists sequentially.