Algorithms & complexity worksheet with answers

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

What does the average-case running time describe?

1. AThe middle value between the best-case and worst-case running times
2. BThe time on the most common computer
3. CThe time for an input of average length
4. DThe expected time over a given distribution of inputs of size n

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

1. AConstant
2. BQuadratic
3. CLogarithmic
4. DLinear

A greedy algorithm:

1. ATries every possible solution
2. BAlways gives the optimal solution
3. CMakes the locally best choice at each step
4. DUses only recursion

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

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

The time complexity of naive recursive Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

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

Why can Dijkstra's algorithm give wrong results when some edge weights are negative?

1. AIt only works on undirected graphs
2. BIt goes into an infinite loop on every negative edge
3. CNegative numbers cannot be stored in a priority queue
4. DA vertex is finalised when extracted, but a later negative edge could still give it a shorter path

What is the time complexity of: for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work?

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