AQA A2 Computing 1.2 Comparing Algorithms Flashcards
Algorithm
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
computational complexity of an algorithm
measures how economical the algorithm is with time and space
Time complexity of an algorithm
indicates how fast an algorithm runs
Space complexity of an algorith
indicates how much memory an algorithm needs
Complexity of a problem
taken to be the worst case complexity of the most efficient algorithm which solves the problem
Basic operation
the operation contributing the most to the total running time
Order of growth
asses by what factor execution time increases when the size of the input is increased
Asymptotic behaviour of f
the behaviour of the function f(n) for very large values of n
0(g)
called big O of g, represents the class of functions that grow no faster than g
Order of complexity
Order of complexity of a problem is its big O complexity
Exponential growth
growth that has the form k^n , e.g. 2^n where k=2 and n=1,2,3, etc
Exponential time algorithm
an alogithm whose execution time grows exponentially with input size
Polynomial growth
growth that has the form n^k e.g. n^3 where k=3 and n=1,2,3,4,etc
Polynomial time algorithm
an algorithm whose execution time grows as a polynomial of input size
Linear time algorithm
a polynomial time algorithm that executes in O(n) time
