Learning objective
Limits of computation: Be aware that algorithmic complexity and hardware impose limits on what can be computed.
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
Limits of computation
Study support
Understand this objective
Quick explanation
Limits of computation: Be aware that algorithmic complexity and hardware impose limits on what can be computed
- This point belongs to Classification of algorithms, especially Limits of computation.
- You need to be able to limits of computation: Be aware that algorithmic complexity and hardware impose limits on what can be computed.
- 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 Limits of computation to exam-style questions, flashcards, and revision notes for Classification of algorithms.
Quick student answer
Which statement best describes a limit imposed by algorithmic complexity?
Direct answer
An algorithm may require too much time as the input size increases
Key terms
- Algorithmic complexity: The way an algorithm's resource requirements, such as processing time or memory, change as the input size increases.
- Hardware limit: A restriction caused by the finite processing speed or memory available in a computer system.
Common trap
Confusing impractical with impossible: State that the computation may be impractical with the current algorithm, input size, time constraint, or hardware. Do not conclude that the problem is impossible without sufficient justification.
Related questions
Try this as a practice card
Question 1 of 4
Choose an answer, get feedback, then move sideways through the set.
Flashcard prompts
Flip through the key recall cards
Flashcard 1 of 4
Revision tools
Choose how to practise
Flashcards0 linked cards
Practice Questions0 linked 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
- 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
- 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