AQA A2 Computing 1.2 Comparing Algorithms Flashcards

1
Q

Algorithm

A

a sequence of unambiguous instructions for solving a problem, i.e. for obtaining a required output for any legitimate input in a finite amount of time. It can be represented as a Turing machine program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

computational complexity of an algorithm

A

measures how economical the algorithm is with time and space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Time complexity of an algorithm

A

indicates how fast an algorithm runs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Space complexity of an algorith

A

indicates how much memory an algorithm needs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Complexity of a problem

A

taken to be the worst case complexity of the most efficient algorithm which solves the problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Basic operation

A

the operation contributing the most to the total running time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Order of growth

A

asses by what factor execution time increases when the size of the input is increased

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Asymptotic behaviour of f

A

the behaviour of the function f(n) for very large values of n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

0(g)

A

called big O of g, represents the class of functions that grow no faster than g

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Order of complexity

A

Order of complexity of a problem is its big O complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Exponential growth

A

growth that has the form k^n , e.g. 2^n where k=2 and n=1,2,3, etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Exponential time algorithm

A

an alogithm whose execution time grows exponentially with input size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Polynomial growth

A

growth that has the form n^k e.g. n^3 where k=3 and n=1,2,3,4,etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Polynomial time algorithm

A

an algorithm whose execution time grows as a polynomial of input size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Linear time algorithm

A

a polynomial time algorithm that executes in O(n) time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly