2.3.1 Analysis, Design & Comparison of Algorithms

Question 1

State two pieces of information used to analyse an algorithm.

Answer 1

Time complexity
Space complexity

Question 2

What is meant by time complexity?

Answer 2

How much time an algorithm requires to solve a particular problem

Question 3

How is time complexity measured?

Answer 3

Using big-o notation

Question 4

What does big-o notation show?

Answer 4

The time taken relative to the number of data elements given as an input

Question 5

How can big-o notation be used?

Answer 5

To predict the amount of time taken to solve an algorithm given the number of elements stored

Question 6

What is the name given to O(1)?

Answer 6

Constant time complexity

Question 7

What is the name given to O(n)?

Answer 7

Linear time complexity

Question 8

What is the name given to O(n²)?

Answer 8

Polynomial time complexity

Question 9

What is the name given to O(nⁿ)?

Answer 9

Polynomial time complexity

Question 10

What is the name given to O(2ⁿ)?

Answer 10

Exponential time complexity

Question 11

What is the name given to O(log n)?

Answer 11

Logarithmic time complexity

Question 12

What is the name given to O(n log n)?

Answer 12

Linearithmic time complexity

Question 13

Describe what is meant by O(1).

Answer 13

The amount of time taken to complete an algorithm is independent from the number of elements inputted

Question 14

Describe what is meant by O(n).

Answer 14

The amount of time taken to complete an algorithm is directly proportional to the number of elements inputted

Question 15

Describe what is meant by O(n²).

Answer 15

The amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted

Question 16

Describe what is meant by O(nⁿ).

Answer 16

The amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n

Question 17

Describe what is meant by O(2ⁿ).

Answer 17

The amount of time taken to complete an algorithm will double with every additional item

Question 18

Describe what is meant by O(log n).

Answer 18

The amount of time taken to complete an algorithm will half with every additional item

Question 19

What is a logarithm?

Answer 19

An operation that determines how many times a certain (base) number is multiplied by itself to reach another number

Question 20

What is meant by space complexity?

Answer 20

The amount of storage an algorithm takes

Question 21

How can space complexity be reduced?

Answer 21

By performing all of the changes on the original pieces of data

Question 22

How can time complexity be reduced?

Answer 22

By reducing the number of embedded loops where possible

Question 23

What time complexity does a linear search algorithm have?

Answer 23

O(n)

Question 24

What time complexity does a binary search algorithm have?

Answer 24

O(log n)

Question 25

What time complexity does a bubble sort algorithm have?

Answer 25

O(n²)