Week 10 Comparing Algorithms

Question 1

List all the time complexities, from most efficient to least

Answer 1

O(1), O(logn), O(n), O(nlogn), On^k), O(k^n), O(n!)

Question 2

What does constant time (O(1)) complexity mean?

Answer 2

As the size of the input/problem increases;
the amount of time taken remains the same;

Question 3

What does linear time (O(n)) complexity mean?

Answer 3

As the size of the input/problem increases;
the amount of time taken increases at the same rate (directly proportional relationship);

Question 4

What can O(n!) be described as?

Answer 4

The number of permutations (ways of arranging) of n

Question 5

What is an intractable problem?

Answer 5

Problem can be solved but only in exponential time (or greater)

Question 6

What is a tractable problem?

Answer 6

Problem can be solved in polynomial time (or less)

Question 7

What is a heuristic algorithm?

Answer 7

Finds a close-to-optimal solution by relaxing the constraints of the problem to reduce the size of the problem space

Question 8

What approaches can we take to try and solve intractable problems?

Answer 8

Use a heuristic algorithm, providing a close-to-optimal solution;
It makes use of estimates based on experience and relaxes some constraints of the problem;

Question 9

State and explain the time complexity of the linear search [3]

Answer 9

O(n);
As the size of the list/problem increases, the time taken increases at the SAME RATE;
The worst-case scenario is that ALL 𝒏 items will be visited (if item is at the end of the list);

Question 10

State and explain the time complexity of the binary search [3]

Answer 10

O(log n);
Each comparison halves the size of the list that has to be searched through;
If the size of the list doubles then the number of comparisons needed only increases by 1;

Question 11

Explain how the Bubble Sort works [3]

Answer 11

On each pass through the list it compares each pair of adjacent items;
If they’re in the wrong order, the items are swapped;
Does at most n passes through the list;

Question 12

State and explain the time complexity of the Bubble Sort [3]

Answer 12

O(n^2);
The algorithm makes (at most) 𝒏 passes through the list;
On each pass 𝒏 items are examined;

Question 13

State two ways to improve the efficiency of the Bubble Sort [2]

Answer 13

**Solution 1: **
Have a flag (Boolean) variable that is set to True if a swap is made and reset to False at the start of each pass.
Change the outer loop so that it would stop repeating if no swaps have been made;

**Solution 2: **
After the inner loop subtract 1 fromits upper limit;
by subtractingthe pass numberfromthe length of the list;

Question 14

State and explain the time complexity of the merge sort [2]

Answer 14

Merge Sort works by repeatedly halving the list into sublists until there are n lists of 1 element.

The halving process takes 𝑶(𝒍𝒐𝒈⁡𝒏) operations;

These sublists are then compared with adjacent sublists and ordered. This takes 𝑶(𝒏) operations;