Algorithms & complexity worksheet with answers

What is the best-case time complexity of insertion sort, on an already sorted array?

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

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

What is the time complexity of binary search on a sorted array?

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

How does Prim's algorithm build a minimum spanning tree?

1. AIt runs breadth-first search and keeps the BFS tree
2. BIt sorts all edges by weight and adds each one unless it would form a cycle in the forest
3. CIt removes the most expensive edge until no cycles remain
4. DIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree

Why do many library sorting routines switch to insertion sort for very small subarrays?

1. ARecursive algorithms cannot handle arrays below 10 elements
2. BInsertion sort is O(n log n) in the worst case
3. CInsertion sort uses less memory than any other sorting algorithm on large inputs
4. DInsertion sort has little overhead and is fast on small or nearly sorted inputs

Why does dynamic programming give no real speed-up for merge sort?

1. ADynamic programming only works on graph problems, not on arrays
2. BMerge sort is already O(n)
3. CMerge sort has no recursive structure
4. DIts subproblems do not overlap, so there is nothing to reuse

A problem is NP-complete if it is:

1. ASolvable in polynomial time
2. BIn NP and every NP problem reduces to it in polynomial time
3. CImpossible to solve
4. DOutside NP but harder than all NP problems, such as the halting problem

What is the time complexity of building a binary heap from n unsorted elements with the bottom-up method?

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