Algorithms & complexity worksheet with answers

Space complexity measures:

1. AThe number of lines of code
2. BThe disk space of the program file once it is compiled
3. CThe amount of memory an algorithm needs as input grows
4. DThe physical size of the computer

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

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

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

1. ABubble sort
2. BHeap sort
3. CQuicksort
4. DMerge sort

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

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

Which statement about a recursive function without a reachable base case is correct?

1. AIt keeps calling itself until the call stack overflows
2. BThe compiler always turns it into a loop that ends safely
3. CIt returns 0 automatically
4. DIt runs in O(1) time

About how many comparisons does binary search need in the worst case on a sorted array of 1,000,000 elements?

1. AAbout 20
2. BAbout 1,000
3. CAbout 100
4. DAbout 500,000

Which of these satisfiability problems is known to be solvable in polynomial time?

1. AGeneral SAT on formulas in conjunctive normal form
2. B3-SAT, where each clause has exactly three literals
3. CCircuit satisfiability
4. D2-SAT, where each clause has at most two literals

The halting problem shows that:

1. AEvery program eventually halts
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. DLoops should be avoided