Lesson 4.4.4.3
4.4.4.3 Order of complexity Quiz: AQA Computer Science, Unit 4
20 questions
In partnership with Revision Ninja
Lesson 4.4.4.3, Order of complexity: 20 multiple choice questions for the AQA Computer Science (7517), Unit 4: Theory of computation, written with Revision Ninja.
Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.
The 20 questions
-
What is the Big-O notation for constant time?
- O(n^2)
- O(1)
- O(n)
- O(log n)
-
Binary search is an example of which order of complexity?
- Logarithmic time
- Exponential time
- Constant time
- Linear time
-
Linear search is an example of which order of complexity?
- Exponential time
- Logarithmic time
- Constant time
- Linear time
-
What time complexity category does a quadratic algorithm belong to?
- Polynomial time
- Exponential time
- Logarithmic time
- Constant time
-
What time complexity results from checking every possible subset of n items?
- Exponential time
- Logarithmic time
- Polynomial time
- Linear time
-
Which growth class is fastest-growing among O(n), O(log n), O(n^2) and O(2^n)?
- O(log n)
- O(n)
- O(2^n)
- O(n^2)
-
A loop runs once for each value of i from 1 to n, with a constant amount of work each time. What is the complexity?
- O(n)
- O(n^2)
- O(log n)
- O(1)
-
Two nested loops each run from 1 to n with constant work in the body. What is the complexity?
- O(n)
- O(n^2)
- O(log n)
- O(2^n)
-
A loop doubles i each iteration from 1 until it reaches n. What is the complexity?
- O(n)
- O(log n)
- O(n^2)
- O(1)
-
The inner loop runs i times for i from 1 to n. What is the total number of inner iterations?
- n
- n(n + 1) / 2
- 2^n
- log n
-
Which Big-O expression describes 3n^2 + 5n + 2?
- O(n^2)
- O(2^n)
- O(n^3)
- O(n)
-
Which Big-O expression describes 7n log n + 100?
- O(n)
- O(log n)
- O(n^2)
- O(n log n)
-
Which time complexity function grows fastest as n approaches infinity?
- Linear
- Cubic
- Quadratic
- Logarithmic
-
An algorithm runs in O(2^n) time. Roughly how many steps does it need for n = 20?
- About 1 million
- 20
- 400
- About 1 billion
-
What happens to constant multipliers in Big-O time complexity expressions?
- They are doubled
- They are ignored
- They are squared
- They are inverted
-
How does execution time change for an O(log n) algorithm when input size doubles?
- Doubles in time
- Halves in time
- Increases by constant
- Quadruples in time
-
How many permutations are there of 5 distinct items?
- 120
- 3125
- 60
- 24
-
Which complexity class grows faster than exponential time O(2^n) for large inputs?
- Factorial time
- Quadratic time
- Logarithmic time
- Polynomial time
-
Which growth rate is strictly slower than quadratic time O(n^2) for large inputs?
- O(n!)
- O(n^3)
- O(n log n)
- O(2^n)
-
What is the Big-O of an algorithm that takes n + log n steps?
- O(n^2)
- O(2^n)
- O(log n)
- O(n)
Related quizzes
- Problem-solving and algorithms Quiz · 4.4.1.1 · 20 questions
- Abstraction Quiz · 4.4.1.3 · 20 questions
- Problem reduction and decomposition Quiz · 4.4.1.8 · 20 questions
- Composition Quiz · 4.4.1.10 · 20 questions
- Automation Quiz · 4.4.1.11 · 20 questions
- Finite state machines Quiz · 4.4.2.1 · 20 questions
- Regular expressions Quiz · 4.4.2.3 · 20 questions
- Backus-Naur Form and syntax diagrams Quiz · 4.4.3.1 · 20 questions
- Comparing algorithms Quiz · 4.4.4.1 · 20 questions
- Limits of computation and computable problems Quiz · 4.4.4.4 · 20 questions