Learning objective
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.
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
Order of complexity
Aqa A Level Computer ScienceTheory of computation
Study support
Understand this objective
Quick explanation
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
- This point belongs to Classification of algorithms, especially Order of complexity.
- You need to be able to 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.
- 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 Order of complexity to exam-style questions, flashcards, and revision notes for Classification of algorithms.
Quick student answer
An algorithm performs a fixed number of instructions, regardless of the size of its input. What is its time complexity?
Direct answer
O(1)
Key terms
- Big-O notation: A notation used to describe the growth of an algorithm's running time as the input size increases.
- Time complexity: A measure of how the running time requirements of an algorithm grow in relation to the size of its input.
Common trap
Counting exact operations instead of growth: Identify how the dominant part of the algorithm grows with n, then ignore constant factors and less significant terms when stating the Big-O classification.
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
- 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.
Maths for understanding Big-0 notation
- 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