Algorithms & complexity worksheet with answers

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

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

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

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

Which notation describes an upper bound on growth?

1. ALittle omega
2. BBig Theta
3. CBig Omega
4. DBig O

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

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

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

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

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

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

The halting problem shows that:

1. AEvery program eventually halts
2. BLoops should be avoided
3. CNo algorithm can decide for every program and input whether it halts
4. DSome programs run faster on faster computers, so halting depends on hardware

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt is undecidable
2. BIt can be solved by Dijkstra's algorithm with negated weights
3. CIt is always solvable in O(V + E)
4. DIt is NP-hard