Algorithms & complexity worksheet with answers

What does it mean if an operation runs in O(1) time?

1. AIt processes exactly one element per second of running time
2. BIt can only be run once
3. CIts running time does not grow with the input size
4. DIt always takes exactly one second

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

1. AConstant
2. BLogarithmic
3. CLinear
4. DQuadratic

How much extra memory does a standard array-based merge sort use?

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

What does the recurrence T(n) = T(n − 1) + O(1) solve to?

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

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

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

In the activity selection problem, which greedy rule always gives a maximum number of non-overlapping activities?

1. APick the activity that starts earliest
2. BPick the activity with the fewest overlaps first, then repeat with the compatible ones
3. CPick the activity that finishes earliest, then repeat with the compatible ones
4. DPick the shortest activity first

What is the difference between an undecidable problem and an intractable one?

1. AIntractable problems cannot be solved by any algorithm, while undecidable ones only need exponential time
2. BAn undecidable problem has no algorithm for all inputs; an intractable one has one, but it is too slow
3. CBoth mean the problem has no algorithm at all
4. DUndecidable problems are in NP, while intractable problems are in P

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

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