Section 8 Chapter 45 - Big-O Notation Flashcards
1
Q
What is a function in terms of mappings
A
It is a mapping from one set of values to another set of values (the domain to the co-domain)
2
Q
Time complexity
A
The time that an algorithm takes to complete
3
Q
Permutations
A
All the different ways of arranging a set of objects
4
Q
Number of permutations
A
n!
5
Q
How to express constant time with Big O notation
A
O(1)
6
Q
How to express linear time with Big O notation
A
O(n)
7
Q
How to work out the time complexity of a function
A
Look for the most important term (ignore all coefficients)
8
Q
How to work out the time complexity of an algorithm
A
X nested for loops means complexity n^X
Splitting the search space into pieces is log(n)
Checking permutations is n!
