Algorithms & complexity worksheet with answers

What is a brute-force algorithm?

1. AOne that always uses recursion
2. BOne that runs on many processors
3. COne that tries all possible candidate solutions
4. DOne that guesses an answer at random

What does the worst-case running time of an algorithm describe?

1. AThe maximum time it takes over all inputs of size n
2. BThe time it takes on the smallest input
3. CThe time it takes on a slow computer
4. DThe expected time it takes on a random input of size n

What is the Big O of 3n² + 5n + 2?

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

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

How many levels does the recursion of merge sort have for an array of n elements?

1. AAbout √n
2. BAbout log₂ n
3. CAbout n / 2
4. DAbout n

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

1. ANeither variant
2. BThe 0/1 knapsack, where items must always be taken whole
3. CBoth variants
4. DThe fractional knapsack, where items may be split

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt is NP-hard
2. BIt is always solvable in O(V + E)
3. CIt can be solved by Dijkstra's algorithm with negated weights
4. DIt is undecidable