Algorithms & complexity worksheet with answers

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

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

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

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

What does the average-case running time describe?

1. AThe expected time over a given distribution of inputs of size n
2. BThe time for an input of average length
3. CThe time on the most common computer
4. DThe middle value between the best-case and worst-case running times

Breadth-first search on an unweighted graph finds:

1. AShortest paths in graphs that contain negative edge weights
2. BThe minimum spanning tree
3. CA topological order in all graphs
4. DShortest paths in number of edges from the start node

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 log n)
3. CO(n)
4. DO(n³)

What is the running time of LSD radix sort on n integers with d digits in base k?

1. AO(dn log k)
2. BO(d(n + k))
3. CO(n²)
4. DO(n log n)

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(2ⁿ) time and O(1) space
2. BO(n) time and O(n) space
3. CO(log n) time and O(n) space
4. DO(n) time and O(1) space

Topological sorting is possible only for:

1. AUndirected graphs
2. BDirected acyclic graphs
3. CComplete graphs
4. DGraphs with negative weights