Algorithms & complexity worksheet with answers

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

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

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

1. AMerge sort
2. BQuicksort
3. CBubble sort
4. DInsertion sort

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 Floyd–Warshall algorithm compute, and how fast?

1. AA topological order in O(V²)
2. BA minimum spanning tree in O(E log V)
3. CShortest paths between all pairs of vertices in O(V³)
4. DShortest paths from one source vertex to all others in O(V + E)

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms with different bases differ only by a constant factor
2. BAll logarithms in computer science have base 10, so it is implied
3. CThe base only matters for small n
4. DLogarithms are always rounded to integers

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(mn)
2. BO(mn log n)
3. CO(2^m+n)
4. DO(m + 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. BBoth variants
3. CThe fractional knapsack, where items may be split
4. DThe 0/1 knapsack, where items must always be taken whole

Why does binary search not give O(log n) time on a singly linked list?

1. ALinked lists cannot be sorted
2. BBinary search needs at least twice the memory
3. CComparisons on linked list nodes are slower
4. DReaching the middle element takes O(n) steps, since there is no direct index access