Python Programming - MCQ Practice Questions

Merge Sort divides the array into halves recursively and merges them in sorted order. Its recurrence is $T(n)=2T(n/2)+O(n)$, which by the Master Theorem gives $\boxed{O(n\log n)}$ in all cases (best, average, and worst).

The Fibonacci sequence is: fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8. The naive recursive approach correctly computes fib(6) = 8, though its time complexity is $O(2^n)$.

Merge Sort requires auxiliary space proportional to the size of the input array to store the temporary merged subarrays. Additionally, the recursion stack uses $O(\log n)$ space, but the dominant term is the auxiliary array, making the total space complexity $\boxed{O(n)}$.

The linear search iterates through [10, 30, 20, 50, 40] using enumerate, which provides (index, value) pairs. The value 50 is found at index 3, so the function returns 3. Note that enumerate is 0-based, so index 3 corresponds to the 4th element.

Insertion Sort builds the sorted array one element at a time. For each element, it shifts larger elements in the sorted portion to the right and inserts the current element in the correct position. Its best-case time complexity is $O(n)$ for a nearly sorted array, and worst case is $O(n^2)$.

The function searches for 7 in [1, 3, 5, 7, 9, 11]. First call: mid = (0+5)//2 = 2, arr[2] = 5 < 7, so search right. Second call: low=3, high=5, mid=4, arr[4]=9 > 7, so search left. Third call: low=3, high=3, mid=3, arr[3]=7 == 7, returns index 3.