Sorting and General

Question 0

What is the best-case time complexity of insertion sort?

Answer 0

O(n)

Question 1

What is the time complexity of insertion sort?

Answer 1

O(n^2)

Question 2

What term describes an algorithm which improves in performance for certain inputs?

Answer 2

Adaptive

Question 3

What input hits the worst case of insertion sort?

Answer 3

Reverse order

Question 4

What input hits the best case of insertion sort?

Answer 4

Already sorted

Question 5

What is the space complexity of insertion sort?

Answer 5

O(1)

Question 6

How can we improve on trickle-down insertion sort?

Answer 6

Instead of swapping all the way down (which uses three assignments per swap), first determine the location to insert at, store a[i] in a temp variable, and trickle up from a[j] (one assignment per iteration)

Question 7

Give the formal definition of what it means for a function f(n) to be O(g(n))

Answer 7

There are constants k,N > 0 such that for all n > N . f(n)

Question 8

Give the informal definition of what it means for a function f(n) to be O(g(n))

Answer 8

f(n) grows at most like g(n)

Question 9

Give the formal definition of what it means for a function f(n) to be θ(g(n))

Answer 9

There are constants j,k,N > 0 such that for all n > N . 0

Question 11

Informally, what does it mean for a function f(n) to be θ(g(n))

Answer 11

f(n) grows exactly like g(n)

Question 12

Informally, what does it mean for a function f(n) to be Ω(g(n))?

Answer 12

f(n) grows at least like Ω(g(n))

Question 13

What do small-letter complexity classes indicate?

Answer 13

A stricter version of the same big-letter classes. E.g. f(n) is o(g(n)) means f(n) grows “strictly more slowly” than g(n)

Question 14

When is amortized analysis useful?

Answer 14

When analysing data structure operations which are performed in sequence

Question 15

What technique can be used to minimise the cost of exchanges when sorting arrays of large chunks of data?

Answer 15

Sorting by proxy: create an array of indices, do comparisons on the data and exchange the indices

Question 16

What is the maximum number of exchanges needed to sort an array?

Answer 16

Θ(n), exactly n-1

Question 17

What is the lower bound on the number of comparisons necessary to sort an array?

Answer 17

Ω(n logn)

Question 18

Give a proof of the lower bound on comparisons necessary to sort an array

Answer 18

There are n! permutations. Consider any two distinct elements in the array, a and b. If we compare a and b then we halve the number of possible permutations. Hence, we must perform lg(n!) = θ(n logn) comparisons (by Stirling’s approximation)

Question 19

Describe selection sort

Answer 19

For each element k in the array, (linearly) find the minimum element in a[k:end] and swap that element with a[k]

Question 20

What is the time complexity of selection sort

Answer 20

O(n^2)

Question 21

What is a good algorithm to use when comparisons are expensive but exchanges are very cheap?

Answer 21

Binary insertion sort - Binary chop is used to guarantee the minimal O(n logn) comparisons - however exchanges are O(n^2).