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

Which of these running times is polynomial?

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

What is log₂ 1024?

1. A10
2. B512
3. C12
4. D32

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

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

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

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

What does it mean that a problem has optimal substructure?

1. AEvery subproblem has the same size
2. BThe problem can be solved in constant time
3. CThe problem has exactly one optimal solution, which every subproblem shares
4. DAn optimal solution can be built from optimal solutions of its subproblems

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

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

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)
2. BO(n log n)
3. CO(n √n)
4. DO(n²)