Algorithms

Question 1

How to check if an algorithm has a specific complexity?

Answer 1

Question 2

Difference between big O, theta, and omega notation?

Answer 2

big O describes the worst-case performance of an algorithm, it may perform better.
big Theta describes the specifically determined performance of an algorithm (down to constant level). E.g. an algorithm with runtime n^2 will always take a constant multiple of n^2 to run.
big Omega describes the best-case performance of an algorithm, it may perform worse.

Question 3

What is a stable sorting algorithm?

Answer 3

If two elements are in a specific order before sorting and have equal values, they will be in the same order afterwards.

Examples are: merge sort, insertion sort and bubble sort.

Question 4

What is the best case runtime for any comparison-based sorting algorithm?

Answer 4

nlogn

Question 5

What does it mean that big Theta is symmetrical?

Answer 5

If f(n) is O(g(n)) then g(n) is O(f(n))

Question 6

Which sorting algorithms are divide-and-conquer?

Answer 6

Quick sort, merge sort, heap sort, binary-tree sort

Question 7

What is counting sort?

Answer 7

For an array with elements with a known maximum value k:
Create a secondary array B with k+1 positions.
Count occurrences of each number in its corresponding place in B.
Replace each number in B with the sum of the numbers before it.
Iterate over original array A, for each value look up the new index in C by indexing into B with the value.
After each insertion, decrement the value in B for that value.

It has runtime O(n).

Question 8

Constructing a heap

Answer 8

Each node in the heap must be bigger than its children. To heapify: traverse the tree from the right side of the array to the left. If node does not fulfil heap property: heapify it.

Question 9

Properties of heap sort?

Answer 9

heapify has runtime O(log n) and heap construction has runtime O(n log n).
Unstable.
In-place.

Question 10

Properties of insertion sort?

Answer 10

In-place.
Stable.
O(n^2)

Question 11

How to do radix sort?

Answer 11

Use an in-place sorting algorithm to sort the array of numbers by each digit individually, starting with the least-significant digit.

Sorts in O(d*f) where f is the runtime of the in-place sorting algorithm, and d is the number of digits in each element.