Unit 1: Analysis of Algorithms and Divide-and-Conquer - Practice Quiz

1 What does the time complexity of an algorithm describe?

2 What does auxiliary space complexity measure?

3 What is the best-case time complexity of insertion sort when the array is already sorted?

4 What is the worst-case time complexity of insertion sort?

5 What is the standard time complexity of merge sort for an array of elements?

6 How much auxiliary space does the standard array-based merge sort use?

7 A loop executes exactly times and performs constant work in each iteration. What is its time complexity?

8 Two nested loops each execute times. If the inner operation takes constant time, what is the total time complexity?

9 What is the purpose of a base case in a recursive algorithm?

10 Which recurrence represents a function that makes one recursive call on input size and performs constant additional work?

11 What is the main idea of the substitution method for solving recurrences?

12 In the recursion tree method, what does each level of the tree represent?

13 For , what is the total work performed at each non-leaf level of the recursion tree?

14 What is the standard form of a recurrence handled by the Master Method?

15 Using the Master Method, what is the solution of ?

16 How many recursive matrix multiplications does Strassen's algorithm use for two partitioned matrices?

17 What is the asymptotic time complexity of Strassen's matrix multiplication algorithm?

18 In a set of distinct elements, what is the first order statistic?

19 What is the average-case time complexity of Quick Select?

20 What is the third smallest element in the array ?

21 Consider the following loops, where is a power of :

for (i = 1; i <= n; i *= 2)

for (j = 0; j < i; j++)

operation();

What are the time and auxiliary space complexities?

22 When insertion sort processes the array , how many element shifts are performed?

23 A standard top-down merge sort uses temporary arrays during merging. What are its worst-case time and auxiliary space complexities?

24 What is the time complexity of the following loop structure?

for (i = 1; i <= n; i++)

for (j = 1; j <= i; j++)

operation();

25 Determine the time complexity of the following code:

for (i = 1; i <= n; i++)

for (j = i; j <= n; j += i)

operation();

26 An algorithm has recurrence with . What is its asymptotic running time?

27 A recursive function makes two calls on inputs of size and performs a loop taking time outside the calls. What is its running time?

28 For , suppose the inductive hypothesis is for . What expression results after substitution and simplification?

29 To prove is , assume . What condition on makes the induction step valid?

30 For the recurrence , how does the nonrecursive cost change from one recursion-tree level to the next, and what is the resulting complexity?

31 Consider . What complexity is indicated by a recursion-tree analysis?

32 Use the Master Method to solve .

33 What is the solution of according to the Master Method?

34 Strassen's algorithm divides each matrix into four blocks but uses seven recursive block multiplications. Which pair correctly describes its recurrence and asymptotic time?

35 An array contains distinct elements. After partitioning, a pivot has exactly elements smaller than it and elements larger than it. Which order statistic is the pivot?

36 Using the pairwise method, what is the minimum number of comparisons needed to find both the minimum and maximum of distinct elements?

37 For randomized Quick Select, which pair correctly states the expected and worst-case running times?

38 Quick Select seeks the th smallest element. After partitioning, the pivot is the th smallest element of the current subarray. What should the algorithm do next?

39 To find the th smallest element in an unsorted array, an algorithm maintains a max-heap containing the smallest values seen so far. What does the heap root represent at the end, and what is the running time?

40 An array of distinct elements is sorted in ascending order and indexed from . At which index is the th largest element?

41 Consider a recursive procedure that makes two calls with parameter until , performs work per call, and stores no results. If output storage is excluded, what are its time and auxiliary-space complexities when called with ?

42 An array of length contains exactly inversions. Insertion sort uses a sentinel, so every insertion performs one final unsuccessful key comparison. What are the exact number of shifts and key comparisons?

43 A top-down merge sort allocates a temporary array proportional to the current subproblem size in each active call and releases it when that call returns. What are its worst-case time and peak auxiliary-space complexities?

44 Determine the running time of the following loop, assuming the body is :

for (i = 1; i <= n; i *= 2)

for (j = i; j <= n; j += i)

body

45 What is the asymptotic running time of the following algorithm?

for (i = 1; i <= n; i++)

for (j = i; j <= n; j += i)

for (k = 1; k <= j; k *= 2)

body

46 For constant-size base cases, determine the tight bound for

47 For , suppose the induction hypothesis is substituted directly, without adding a lower-order term. Which condition on makes the inductive inequality hold for all sufficiently large ?

48 Let be a power of two and consider



with a constant-size base case. What bound follows from a recursion-tree analysis?

49 Using the Master Method, determine the tight bound for

50 Consider



Which statement is correct?

51 Strassen's algorithm is applied to two matrices where is not a power of two. Each matrix is padded to size , where is the next power of two. What is the resulting asymptotic running time in terms of ?

52 At recursion level of Strassen's algorithm, there are subproblems of dimension . What is the total matrix-addition work at that level?

53 In the comparison model, what is the optimal worst-case number of comparisons needed to find both the minimum and maximum of elements?

54 Quick Select repeatedly chooses a pivot that is the smallest remaining element while searching for the largest element. What recurrence and worst-case running time result?

55 For randomized Quick Select on an arbitrary fixed input, where each pivot is chosen uniformly from the active subarray, which pair of bounds is correct?

56 Two arrays of lengths and are individually sorted. Without merging them, what time and auxiliary-space bounds can a binary-partition algorithm achieve for finding the -th smallest element?

57 A three-way partition around pivot produces elements greater than , elements equal to , and the rest smaller than . For ranks counted with multiplicity, when is the -th largest element?

58 Suppose deterministic selection groups elements in threes, recursively finds the median of the group medians, and partitions around it. Ignoring rounding, which recurrence describes the standard worst-case analysis, and what bound does it yield?

59 An algorithm scans unsorted elements while maintaining a min-heap containing the largest elements seen so far. What are its worst-case time and auxiliary-space complexities?

60 In median-of-medians selection with groups of five, which worst-case recurrence correctly captures the pivot-selection call and the largest possible recursive partition, up to constant rounding terms?