Algorithms & complexity worksheet with answers

What is the time complexity of depth-first search on a graph stored as adjacency lists?

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

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

1. AInsertion sort
2. BBubble sort
3. CQuicksort
4. DMerge sort

A problem is usually called tractable if:

1. AIt can only be solved by trying every possibility
2. BIt has no solution
3. CIt can be solved in polynomial time
4. DIt can be solved in constant time

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array of length 2
2. BAn array that is already sorted
3. CAn array in random order
4. DAn array whose elements are all different

What is the time complexity of: for i = 1 to n: for j = 1 to i: do O(1) work?

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

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

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

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

1. AThe fractional knapsack, where items may be split
2. BNeither variant
3. CThe 0/1 knapsack, where items must always be taken whole
4. DBoth variants

What does the recurrence T(n) = 2T(n/2) + n log n solve to?

1. AΘ(n log n)
2. BΘ(n)
3. CΘ(n log² n)
4. DΘ(n²)