Algorithms & complexity worksheet with answers

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

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

Which of these grows slowest as n becomes large?

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

An algorithm's running time is O(n). What is this growth called?

1. AQuadratic
2. BLogarithmic
3. CLinear
4. DConstant

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

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

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

Which sorting algorithm is stable?

1. ASelection sort (typical version)
2. BMerge sort
3. CHeap sort
4. DQuicksort (typical in-place version)

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

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

The halting problem shows that:

1. ALoops should be avoided
2. BNo algorithm can decide for every program and input whether it halts
3. CSome programs run faster on faster computers, so halting depends on hardware
4. DEvery program eventually halts