Algorithms & complexity worksheet with answers

Which of these grows slowest as n becomes large?

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

How does selection sort work?

1. AIt repeatedly finds the minimum of the unsorted part and swaps it to the front
2. BIt splits the array in halves and merges them
3. CIt inserts each element into a growing sorted part by shifting
4. DIt repeatedly swaps neighbouring elements that are in the wrong order

A problem is usually called tractable if:

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

The lower bound for comparison-based sorting in the worst case is:

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

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

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

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

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

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

Which definition of the class NP is correct?

1. ADecision problems whose yes-answers can be verified in polynomial time given a certificate
2. BProblems that are not polynomial
3. CProblems that no algorithm can solve
4. DProblems that cannot be solved in polynomial time