Algorithms & complexity worksheet with answers

What is the time complexity of depth-first search on a graph stored as adjacency lists?

1. AO(V × E)
2. BO(E log V)
3. CO(V + E)
4. DO(V²)

Which of these grows slowest as n becomes large?

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

What does binary search require of its input?

1. AThe array length must be a power of two
2. BThe array must contain only positive numbers
3. CThe array must have no more than 1000 elements
4. DThe array must be sorted

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

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

Dynamic programming is useful when a problem has:

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

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n log n)
4. DΘ(n²)

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

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