NEW
Font size
WorksheetsQuiz – Unit 1: Algorithm Analysis
Total questions: 21
Worksheet time: 11mins
What does the complexity of an algorithm measure?
The programming language used
The time and space required based on input
The number of variables used
The aesthetics of the code
What does O big (O(f(n))) mean?
Lower bound of the algorithm
Asymptotic upper bound
Exact execution time
Average execution time
If an algorithm has T(n) = 5n + 3, what is its order of complexity?
Θ(1)
Θ(log n)
Θ(n)
Θ(n²)
Which of the following functions grows faster for large n?
n log n
n²
log n
n
In asymptotic notation, what does Θ(f(n)) represent?
Only upper bound
Only lower bound
Tight bound: both upper and lower
Average time
Order the functions from least to greatest growth:
log n < n < n² < 2ⁿ
n² < log n < n < 2ⁿ
2ⁿ < n² < n < log n
n < log n < 2ⁿ < n²
An algorithm with two nested loops from 0 to n has complexity:
Θ(n)
Θ(n²)
Θ(n log n)
Θ(log n)
An algorithm that divides the problem in half at each step (like binary search) has complexity:
Θ(n²)
Θ(n log n)
Θ(n)
Θ(log n)
The cost of traversing an array of size n is:
Θ(1)
Θ(log n)
Θ(n)
Θ(n²)
The cost of mergesort is given by the recurrence T(n)=2T(n/2)+Θ(n). Its complexity is:
Θ(n²)
Θ(n log n)
Θ(log n)
Θ(n³)
What is the rule for simplifying time equations?
Keep all terms
Eliminate the dominant term
Keep the dominant term
What is the rule for simplifying time equations?
Conserve all terms
Eliminate the dominant term
Conserve the dominant term and eliminate constants
Use only the worst case
The sum of the first n integers is (1 + 2 + ... + n):
Θ(n)
Θ(log n)
Θ(n²)
Θ(2ⁿ)
The average complexity of linear search in a list of n elements is:
Θ(1)
Θ(log n)
Θ(n/2) or Θ(n)
Θ(n²)
The difference between the best and worst case of linear search is:
None
Best case Θ(1), worst case Θ(n)
Best case Θ(log n), worst case Θ(n²)
Best case Θ(n), worst case Θ(1)
Quickselect finds the k-th smallest in:
Θ(n²) always
Θ(n log n) average
Θ(n) average
Θ(log n) worst case
A tree with n nodes has how many edges?
n²
n+1
n-1
2n
The in-order traversal of a binary tree visits nodes in the order:
Root - Left - Right
Left - Root - Right
Right - Root - Left
Root - Right - Left
The complexity of traversing a binary tree of n nodes is:
Θ(log n)
Θ(n)
Θ(n²)
Θ(1)
The complexity of BFS in a graph represented with adjacency lists is:
Θ(V²)
Θ(E)
Θ(V + E)
Θ(log V)
In an adjacency matrix of a graph with V vertices, the required space is:
Θ(V + E)
Θ(V²)
Θ(E)
Θ(1)
