2.3.1 - Algorithms (Big-O)

Question 1

What is the purpose of Big-O

Answer 1

• Used to measure the efficiency/complexity of an algorithm.
• Can be used to measure the speed and/or memory requirements of an algorithm.
• N represents the number of items/elements.

Question 2

Name and describe the complexity shown below

Answer 2

Logarithmic Complexity

Describes an algorithm whose growth rate decreases as the size of the data set increases, following a logarithmic curve. Scales well.

Example: Good for large data sets. A binary search where searching 200 values will just need one more iteration than if the data set only contained 100 values.

Question 3

Name and describe the complexity shown below

Answer 3

Linear Complexity
Describes an algorithm where the execution time grows in direct proportion to the size of the data set it is processing

Example: Algorithms, which are based on a single loop to iterate through each value of the data set (Linear Search)

Question 4

Name and describe the complexity shown below

Answer 4

Exponential Complexity

Describes an algorithm whose growth doubles with each addition to the data set. One item might take 1 second, two items would take two seconds, three items 4 seconds, and so on…

Example: Intractable Problems i.e. Travelling Salesperson

Question 5

Name and describe the complexity shown below

Answer 5

Constant Complexity

Describes an algorithm that will always execute in the same execution time regardless of the size of the data set

Example: Returning the first item in an array, this remains the same regardless of the size of the array.

Question 6

Name and describe the complexity shown below

Answer 6

Polynomial Complexity

Include quadratic algorithms O(N2), cubic algorithms O(N3) and so on… proportional to the polynomial of n

Example: Algorithms which are based onnested loopsare more likely to have a quadratic O(N2), or cubic O(N3) depending on the level of nesting used.

Question 7

What are the possibles cases for the execution time of an algorithm.

Answer 7

The BEST CASE running time of an algorithm is the function defined by the minimum number of steps taken on any instance of size n.

The WORST CASE running time of an algorithm is the function defined by the maximum number of steps taken on any instance of size n.

The AVERAGE CASE running time of an algorithm is the function defined by an average number of steps taken on any instance of size n.

Question 8

Give an example of the best and worst case for a bubble sort.

Answer 8

Best Case - The array is order in order, so just requires one pass through.

Worst Case - The array is in the total opposite order to the one required

Question 9

What is the order of the complexities ranked from best to worst

Answer 9

BEST
Constant
Logarithmic
Linear
Polynomial
Exponential
WORST

Question 10

Which algorithm/s has the following Big-O profile?

Answer 10

Linear Search

Question 11

Which algorithm/s has the following Big-O profile?

Answer 11

Merge Sort

Question 12

Which algorithm/s has the following Big-O profile?

Answer 12

Bubble and Insertion Sort

Question 13

Which algorithm/s has the following Big-O profile?

Answer 13

Quick Sort

Question 14

Which algorithm/s has the following Big-O profile?

Answer 14

Binary Search