4.4.4 Classification of Algorithms

Question 1

What is used to compare algorithms?

Answer 1

Space and time complexity.

Question 2

What are the four methods of comparing algorithms?

Answer 2

Factorials (permutations)
Big O notation.
Function mapping
Time vs space complexity.

Question 3

What is big o notation used for?

Answer 3

Describing the complexity of an algorithm, always assuming the worst case scenario.

Question 4

What is the big o notation for linear search.

Answer 4

O(n)

Question 5

What is the big O notation for bubble sort.

Answer 5

O(n2)

Question 6

What is the big o notation for merge sort

Answer 6

O(nlog(n))

Question 7

What is the big O notation for binary search?

Answer 7

O(log(little2(n))

Question 8

What are the two measurements of the limitations of computation.

Answer 8

Tractability and intractability

Question 9

Define a tractable problem

Answer 9

Have a polynomial or less time solution.

Question 10

On a graph, what do all functions, except constant, grow by?

Answer 10

All functions grow, as the input increases.

Question 11

What is the big o notation for constant?

Answer 11

O(c)

Question 12

What is the big O notation for logarithmic?

Answer 12

O(log(small2(n))

Question 13

What is the big o notation for linear?

Answer 13

O(n)

Question 14

What is the big o notation for linear logarithmic?

Answer 14

O(nlog(n))

Question 15

What is the big o notation for polynomial?

Answer 15

O(n^2)

Question 16

What is the second big o notation for polynomial, in terms of checking 3D coordinates?

Answer 16

O(n^3)

Question 17

What is the big o notation for exponential?

Answer 17

O(2^n)

Question 18

What is the big o notation for factorial?

Answer 18

O(n!)

Question 19

What is a tractable problem?

Answer 19

A problem that can be solved within a useful period of time.

Question 20

What is an intractable problem?

Answer 20

Effectively insoluble problems as they take too long to solve which is unlikely to be useful - due to the limitations of computation.

Question 21

How can intractable problems be solved?

Answer 21

Using heuristics to provide an approximate solution to a problem.

Question 22

What is the problem with using heuristics as a method of solving intractable problems.

Answer 22

They are not optimal and are only approximate solutions.

Question 23

What does the halting problem demonstrate?

Answer 23

That there are some problems which can not be solved by computers.

Question 24

What are factorials useful for?

Answer 24

Calculating permutations.

Question 25

What is the halting problem?

Answer 25

It is impossible to write an algorithm to determine if another algorithm will finish with a given input.

Question 26

What is Computability?

Answer 26

Whether a problem can be solved or not.

Question 27

What is feasability?

Answer 27

How efficiently a problem can be solved

Question 28

What is time as a measurement of feasibility?

Answer 28

How long the algorithm takes to execute.

Question 29

What is space as a measure of feasabiltiy?

Answer 29

How much memory the algorithm used for the storage of data during execution.

Question 30

What happens when more than one algorithm exists?

Answer 30

There can be a trade off between time and space efficiency. One may be quicker but requires more memory than another.

Question 31

How do we measure efficiency?

Answer 31

The amount of space and time depends on the numbers of inputs to a specific algorithm.

Question 32

How do we express efficiency:

Answer 32

A function of the numbers of inputs to algorithms aka N

Question 33

In terms of time complexity, what are the influencing factors?

Answer 33

Processor clock speed.
Efficiency of hardware implementation of operations used.
Other processes executing concurrently.

Question 34

What does big o notation focus on?

Answer 34

The algorithm rather than the hardware that is being executed on.

Question 35

Outline the best case scenario.

Answer 35

An initial list is already ordered and the algorithm terminates after on iteration.