Algorithms & complexity worksheet with answers

What is the Big O of 3n² + 5n + 2?

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

What does the worst-case running time of an algorithm describe?

1. AThe time it takes on the smallest input
2. BThe time it takes on a slow computer
3. CThe maximum time it takes over all inputs of size n
4. DThe expected time it takes on a random input of size n

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

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

What is the worst-case time complexity of quicksort?

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

What does the recurrence T(n) = 2T(n/2) + O(1) solve to?

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

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

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

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

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

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

1. AThe 0/1 knapsack, where items must always be taken whole
2. BThe fractional knapsack, where items may be split
3. CBoth variants
4. DNeither variant