Algorithms & complexity worksheet with answers

Accessing an element by index in an array takes:

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

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

1. AQuicksort
2. BBubble sort
3. CMerge sort
4. DHeap sort

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)

A greedy algorithm:

1. AUses only recursion
2. BMakes the locally best choice at each step
3. CAlways gives the optimal solution
4. DTries every possible solution

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. AYes, but only if n is smaller than 100
2. BNo, because n³ is smaller than n² for large n
3. CYes, because Big O is an upper bound and n² grows no faster than n³
4. DNo, because Big O must always state the exact growth rate of the function

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. BAll logarithms in computer science have base 10, so it is implied
3. CLogarithms with different bases differ only by a constant factor
4. DThe base only matters for small n

Taking both endpoints of every edge in a maximal matching gives a vertex cover. How good is this cover?

1. AOf unknown quality compared to the optimum
2. BAt most twice the size of a minimum vertex cover
3. CAt most log n times the minimum
4. DAlways a minimum vertex cover

Which bound is correct for log(n!)?

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