Algorithms & complexity worksheet with answers

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

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

Which of these running times is polynomial?

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

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

1. AMerge sort
2. BQuicksort
3. CHeap sort
4. DBubble sort

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms with different bases differ only by a constant factor
2. BThe base only matters for small n
3. CAll logarithms in computer science have base 10, so it is implied
4. DLogarithms are always rounded to integers

How many levels does the recursion of merge sort have for an array of n elements?

1. AAbout log₂ n
2. BAbout n
3. CAbout n / 2
4. DAbout √n

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

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

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

1. A2-SAT, where each clause has at most two literals
2. BGeneral SAT on formulas in conjunctive normal form
3. C3-SAT, where each clause has exactly three literals
4. DCircuit satisfiability

Topological sorting is possible only for:

1. ADirected acyclic graphs
2. BUndirected graphs
3. CComplete graphs
4. DGraphs with negative weights