Algorithms & complexity worksheet with answers

What is the base case of a recursive function?

1. AThe call that uses the most memory
2. BA case that is answered directly without making another recursive call
3. CThe case with the largest input, which is handled before any recursive calls
4. DThe first line of the function

What is an algorithm?

1. AA data structure that stores numbers
2. BAny computer program that has a graphical interface
3. CA finite sequence of well-defined steps that solves a problem
4. DA programming language designed for writing mathematical formulas

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

1. AO(n²)
2. BO(log n)
3. CO(n log n)
4. DO(n)

Which statement about a recursive function without a reachable base case is correct?

1. AIt runs in O(1) time
2. BIt keeps calling itself until the call stack overflows
3. CIt returns 0 automatically
4. DThe compiler always turns it into a loop that ends safely

What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

1. AO(E log V)
2. BO(V × E)
3. CO(V + E)
4. DO(V³ × E)

In the activity selection problem, which greedy rule always gives a maximum number of non-overlapping activities?

1. APick the shortest activity first
2. BPick the activity with the fewest overlaps first, then repeat with the compatible ones
3. CPick the activity that starts earliest
4. DPick the activity that finishes earliest, then repeat with the compatible ones

What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?

1. AO(n) time and O(n) space
2. BO(2ⁿ) time and O(1) space
3. CO(log n) time and O(n) space
4. DO(n) time and O(1) space

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. AChoosing the pivot uniformly at random
2. BAlways choosing the first element
3. CSorting the input before running quicksort
4. DUsing recursion only on the left side