Learning objective
Maths for understanding Big-0 notation: Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ. 60 Be familiar with the concept of: • a linear function, for example y = 2x • a polynomial function, for example y = 2x 2 • an exponential function, for example y = 2x • a logarithmic function, for example y = log10 x. Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!). n! is the product of all positive integers less than or equal to n.
Read the explanation, check the common trap, then practise with flashcards and questions.
At a glance
0
Flashcards
0
Questions
Topic
Classification of algorithms
Subtopic
Maths for understanding Big-0 notation
Aqa A Level Computer ScienceTheory of computation
Study support
Understand this objective
Quick explanation
Maths for understanding Big-0 notation: Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ. 60 Be familiar with the concept of: • a linear function, for example y = 2x • a polynomial function, for example y = 2x 2 • an exponential function, for example y = 2x • a logarithmic function, for example y = log10 x. Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!). n! is the product of all positive integers less than or equal to n
- This point belongs to Classification of algorithms, especially Maths for understanding Big-0 notation.
- You need to be able to maths for understanding Big-0 notation: Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ. 60 Be familiar with the concept of: • a linear function, for example y = 2x • a polynomial function, for example y = 2x 2 • an exponential function, for example y = 2x • a logarithmic function, for example y = log10 x. Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!). n! is the product of all positive integers less than or equal to n.
- Use the linked flashcards and practice questions to check recall, then practise applying the idea in an exam-style answer.
Why it matters
This objective helps connect Maths for understanding Big-0 notation to exam-style questions, flashcards, and revision notes for Classification of algorithms.
Quick student answer
Which statement best describes a function written as ℕ → ℕ?
Direct answer
It maps values from the natural numbers to values from the natural numbers
Key terms
- Domain: The set of values supplied as inputs to a function.
- Permutation: An arrangement of a set of distinct objects or values; n distinct objects have n! permutations.
Common trap
Confusing exponential and polynomial functions: In y = 2x², x is raised to a power, so it is polynomial. In y = 2ˣ, x is the exponent, so it is exponential.
Related questions
Try this as a practice card
Question 1 of 4
Choose an answer, get feedback, then move sideways through the set.
0 of 4 attempted
Flashcard prompts
Flip through the key recall cards
Flashcard 1 of 4
Press Space to flip, arrows to move
Revision tools
Choose how to practise
Flashcards0 linked cards
No objective-specific flashcards are cached for this page. Use the topic hub to revise the surrounding flashcards without triggering a frozen-subject DB fallback.Open topic hub
Practice Questions0 linked questions
No objective-specific practice questions are cached for this page. Use the topic question bank to practise nearby curriculum questions without weakening the egress guard.Open topic questions
Related learning objectives
- Comparing algorithms: Understand that algorithms can be compared by expressing their complexity as a function relative to the size of the problem. Understand that the size of the problem is the key issue. Understand that some algorithms are more efficient: • time-wise than other algorithms • space-wise than other algorithms. Efficiently implementing automated abstractions means designing data models and algorithms to run quickly while taking up the minimal amount of resources such as memory.
Comparing algorithms
- Order of complexity: Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in: • constant time • logarithmic time • linear time • polynomial time • exponential time. Be able to derive the time complexity of an algorithm.
Order of complexity
- Limits of computation: Be aware that algorithmic complexity and hardware impose limits on what can be computed.
Limits of computation
- Classification of algorithmic problems: Know that algorithms may be classified as being either: • tractable - problems that have a polynomial (or less) time solution are called tractable problems. • intractable - problems that have no polynomial (or less) time solution are called intractable problems. Heuristic methods are often used when tackling intractable problems.
Classification of algorithmic problems
- Computable and non-computable problems: Be aware that some problems cannot be solved algorithmically.
Computable and non-computable problems