Data Structures and Algorithms

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.

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.

Merge sort has O(n log n) complexity because it divides the array in half log n times (the divide step) and merges n elements at each level (the conquer step). This gives n × log n operations.

Algorithm efficiency is measured by counting the number of key operations (like comparisons, assignments, etc.). Counting microseconds is machine-dependent, making it unreliable for comparing algorithms across different platforms.

Quick sort is a classic divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array around it, then recursively sorting the sub-arrays. Bubble sort and insertion sort are incremental comparison-based sorts. Option D is incorrect because not all sorting algorithms use divide-and-conquer.

Recursion is when an algorithm calls itself directly or indirectly to solve a problem by breaking it down into smaller instances of the same problem. Option A is not a standard term. Option C is a notation for writing expressions. Option D is a type of algorithm for visiting nodes in a data structure, not a general concept.

In a threaded binary tree, null pointers are replaced with 'threads' that point to predecessor or successor nodes in the in-order traversal sequence. This allows efficient traversal without recursion or a stack. Option A (leaf) is a node with no children. Option B (branch) is not standard terminology. Option C (path) refers to a sequence of nodes.

In-order traversal of a binary search tree visits nodes in ascending order of their keys because of the BST property: left child < parent < right child. This is a fundamental property of BSTs. Option A is incorrect because regular binary trees have no ordering property. Option C is incorrect because heaps have different ordering properties.

Strings, lists, and stacks are all linear data structures where elements are arranged sequentially. Option D 'None of above' is correct because the question asks for a NON-linear data structure, but all options A, B, and C are linear types. Examples of non-linear structures would be trees, graphs, or heaps.

Strings, lists, and queues are all linear data structures where elements are accessed in sequential order. Linear structures have a single path to access elements (first-to-last or last-to-first). Since all three options (A, B, C) are linear data structures, option D 'All of above' is correct.

Converting a binary tree to a 2-tree (extended binary tree) requires replacing every null child reference with an external node (leaf placeholder). This creates a strictly binary tree where every internal node has exactly two children, making path length analysis more tractable.