Section 12: Algorithms

Question 1

Define what an algorithm with constant complexity is.

Answer 1

An algorithm with constant complexity is one that always executes in the same time regardless of the size of the data set.

Question 2

What is the big O notation for constant complexity?

Answer 2

Constant complexity:

O(1)

Question 3

Define what an algorithm with logarithmic complexity is.

Answer 3

An algorithm with logarithmic complexity is an algorithm that halves the data set in each pass (opposite to exponential).

Question 4

What is the big O notation for logarithmic complexity?

Answer 4

Logarithmic complexity:

O(log n)

Question 5

Define what an algorithm with linear complexity is.

Answer 5

An algorithm with linear complexity is an algorithm thats performance is proportional to the size of the data set and declines as the data set grows.

Question 6

What is the big O notation for linear complexity?

Answer 6

Linear complexity:

O(n)

Question 7

Define what an algorithm with polynomial complexity is.

Answer 7

An algorithm with polynomial complexity is an algorithm thats performance is proportional to the square of the size of the data set. It becomes significantly more inefficient as the size of the data set grows.

Question 8

What is the big O notation for polynomial complexity?

Answer 8

Polynomial complexity:

O(n^k) where k is the number of nested loops.

Question 9

Define what an algorithm with exponential complexity is.

Answer 9

An algorithm with exponential complexity is an algorithm thats time complexity doubles with each addition to the data set (opposite to logarithmic).

Question 10

What is the big O notation for exponential complexity?

Answer 10

Exponential complexity:

O(2^n)

Question 11

What is the worst case time complexity for a linear search?

Answer 11

Linear search big O:

O(n)

Question 12

What is the worst case time complexity for a binary search?

Answer 12

Binary search big O:

O(log n)

Question 13

What is the worst case time complexity for traversing a binary tree?

Answer 13

Binary tree traversal big O:

O(n)

Question 14

What is the worst case time complexity for a bubble sort?

Answer 14

Bubble sort big O:

O(n^2)

Question 15

What is the worst case time complexity for an insertion sort?

Answer 15

Insertion sort big O:

O(n^2)

Question 16

What is the time complexity for a recursive function calling itself twice?

Answer 16

Recursive function big O:

O(2^n)

Question 17

How does a merge sort work?

Answer 17

A merge sort uses a divide and conquer approach, by splitting a list into sublists until each sublist contains only one element. The smaller sublists are then repeatedly merged together in the correct order, until finally there is a completely sorted list of the same size as the original one.

Question 18

What is the time complexity for a merge sort?

Answer 18

Merge sort big O:

O(n log n)

Question 19

What is the space complexity for a merge sort?

Answer 19

A merge sort requires 2n of memory, where n is the size of the list, since the two halves require additional space.

Question 20

How does a quick sort work?

Answer 20

A quick sort works using a divide and conquer method.
A pivot value is chosen which is then compared with the rest of the items in the list using a left and right pointer.
The list is then divided into two partitions once the two pointers cross - the first containing all values less than the pivot value and the second containing all values greater than the pivot value.
This process is then repeated recursively until the list is sorted.

Question 21

Why can the quick sort be advantageous over the merge sort?

Answer 21

The quick sort is as fast, i.e. O(n logn), but does not require the additional memory that a merge sort does.

Question 22

What is a potential disadvantage of the quick sort?

Answer 22

Quick sorts can be very slow if the split point is not in a useful place. If the split point is very close to the start or the end of the list, there will be a lot more recursion and the time complexity could be O(n^2)

Question 23

What is Dijkstra’s shortest path algorithm?

Answer 23

Dijkstra’s algorithm is an algorithm designed to find the shortest possible path between one particular start node and all other nodes in a weighted graph.

Question 24

How does Dijkstra’s algorithm work?

Answer 24

Firstly, it assigns a temporary distance value to each of the nodes, with the starting node being 0 and the rest being infinity.
Then, all of the nodes are added to a priority queue in order of distance with the starting node being first and the rest in a random order.
After this, each of the nodes are iteratively analysed and their current distance value is compared to the distance between the 2 nodes to check if it is smaller.
This is done until all the nodes have been checked (in a brute force type manner) and the shortest path has been found.

Question 25

How does the A* algorithm differ from Dijkstra’s algorithm?

Answer 25

The crucial difference between the A* and Dijkstra’s path-finding algorithms is that the A* algorithm has an extra cost function - that of the approximate cost of moving from the source node to the goal node. Dijkstra’s algorithm, alternatively, only takes into account the cost function from the source node to any given node.