Algorithms & complexity worksheet with answers

Space complexity measures:

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

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

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

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

Dynamic programming is useful when a problem has:

1. AOnly random inputs
2. BOverlapping subproblems and optimal substructure
3. CA single loop
4. DNo subproblems at all, so it can be solved in one step

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 uses less memory than any other sorting algorithm on large inputs
3. CInsertion sort is O(n log n) in the worst case
4. DInsertion sort has little overhead and is fast on small or nearly sorted inputs

Which statement about little-o notation is correct?

1. A2n = o(n), because 2n grows slowly
2. Bn = o(n²), but n is not o(n)
3. Cn² = o(n)
4. Dn = o(n), since every function is little-o of itself

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

1. AO(n!)
2. BO(n³)
3. CO(2^n²)
4. DO(n² 2ⁿ)