WorksheetsMega Tractability Review
Total questions: 59
Worksheet time: 30mins
Name
Class
Date
1.
Finding the shortest route between twenty the cities is...
a)
tractable
b)
intractable
2.
What is the complexity of the knapsack problem?
a)
exponential O(2^n)
b)
constant O(1)
c)
linear O(n)
d)
quadratic O(n^2)
e)
logarithmic O(log n)
3.
What is the complexity of selection sort?
a)
quadratic O(n^2)
b)
constant O(1)
c)
linear O(n)
d)
logarithmic O(log n)
e)
linearithmic O(n log n)
4.
What is the complexity of quick sort?
a)
linearithmic O(n log n)
b)
constant O(1)
c)
linear O(n)
d)
quadratic O(n^2)
e)
logarithmic O(log n)
5.
What is the complexity of binary search?
a)
logarithmic O(log n)
b)
constant O(1)
c)
linear O(n)
d)
quadratic O(n^2)
e)
linearithmic O(n log n)
6.
What is the complexity of linear search?
a)
linear O(n)
b)
constant O(1)
c)
quadratic O(n^2)
d)
logarithmic O(log n)
e)
linearithmic O(n log n)
7.
Which of the equations below have an O(1) complexity?
a)
y = 2x
b)
y = x!
c)
y = x
d)
y = 7
8.
Which of the following is an example of a problem with a complexity of O(1)?
a)
Finding the shortest route between a series of cities by working out each route and choosing the shortest.
b)
Looking for an item in a box by opening one box at a time (unsorted)
c)
Looking for an item using a binary search strategy (sorted items only)
d)
Retrieving a value from a list using it's index
e)
Sorting items by comparing each item with every other item (selection sort)
9.
Whath is the best case for an algorithm that has a constant complexity?
a)
O(1)
b)
O(n)
c)
O(log n)
d)
O(n log n)
e)
O(2^n)
10.
Whath is the average case for an algorithm that has a constant complexity?
a)
O(1)
b)
O(n)
c)
O(log n)
d)
O(n log n)
e)
O(2^n)
11.
Whath is the worst case for an algorithm that has a constant complexity?
a)
O(1)
b)
O(n)
c)
O(log n)
d)
O(n log n)
e)
O(2^n)
12.
Which rule describes a constant complexity?
a)
As the number of cases doubles, the time needed stays the same
b)
As the number of cases doubles, the time needed increases by one
c)
As the number of cases doubles, the time needed doubles
d)
As the number of cases doubles, the time needded increases four times
13.
Which graph below has a complexity of O(1)?
a)
Option 1
b)
Option 2
c)
Option 3
d)
Option 4
e)
Option 5
14.
Which of the equations below have an O(n) complexity? Choose ALL the correct answers.
a)
y = 2x
b)
y = x!
c)
y = x
d)
y = 7
15.
Which of the following is an example of a problem with a complexity of O(n)?
a)
Finding the shortest route between a series of cities by working out each route and choosing the shortest.
b)
Looking for an item in a box by opening one box at a time (unsorted)
c)
Looking for an item using a binary search strategy (sorted items only)
d)
Retrieving a value from a list using it's index
e)
Sorting items by comparing each item with every other item (selection sort)
16.
Whath is the best case for an algorithm that has a linear complexity?
a)
O(1)
b)
O(n)
c)
O(log n)
d)
O(n log n)
e)
O(2^n)
17.
Whath is the average case for an algorithm that has a linear complexity?
a)
O(n)
b)
O(1)
c)
O(log n)
d)
O(n log n)
e)
O(2^n)
18.
Whath is the worst case for an algorithm that has a linear complexity?
a)
O(n)
b)
O(1)
c)
O(log n)
d)
O(n log n)
e)
O(2^n)
19.
Which rule describes linear complexity?
a)
As the number of cases doubles, the time needed stays the same
b)
As the number of cases doubles, the time needed increases by one
c)
As the number of cases doubles, the time needed doubles
d)
As the number of cases doubles, the time needded increases four times
20.
Which graph below has a complexity of O(n)?
a)
Option 1
b)
Option 2
c)
Option 3
d)
Option 4
e)
Option 5
21.
Which of the equations below have an O(log n) complexity? Choose ALL the correct answers.
a)
y = 2x
b)
y = x!
c)
y = log x
d)
y = 7
22.
Which of the following is an example of a problem with a complexity of O(log n)?
a)
Finding the shortest route between a series of cities by working out each route and choosing the shortest.
b)
Looking for an item in a box by opening one box at a time (unsorted)
c)
Looking for an item using a binary search strategy (sorted items only)
d)
Retrieving a value from a list using it's index
e)
Sorting items by comparing each item with every other item (selection sort)
23.
Whath is the best case for an algorithm that has a logarithmic complexity?
a)
O(1)
b)
O(n)
c)
O(log n)
d)
O(n log n)
e)
O(2^n)
24.
Whath is the average case for an algorithm that has a logarithmic complexity?
a)
O(log n)
b)
O(1)
c)
O(n)
d)
O(n log n)
e)
O(2^n)
25.
Whath is the worst case for an algorithm that has a logarithmic complexity?
a)
O(log n)
b)
O(1)
c)
O(n)
d)
O(n log n)
e)
O(2^n)
26.
Which rule describes logarithmic complexity?
a)
As the number of cases doubles, the time needed stays the same
b)
As the number of cases doubles, the time needed increases by one
c)
As the number of cases doubles, the time needed doubles
d)
As the number of cases doubles, the time needded increases four times
27.
Which graph below has a complexity of O(log n)?
a)
Option 1
b)
Option 2
c)
d)
Option 4
e)
Option 5
28.
Which of the following is an example of a problem with a complexity of O(n log n)?
a)
Finding the shortest route between a series of cities by working out each route and choosing the shortest.
b)
Using quick sort to put boxes in order from lowest to highest
c)
Looking for an item using a binary search strategy (sorted items only)
d)
Retrieving a value from a list using it's index
e)
Sorting items by comparing each item with every other item (selection sort)
29.
What is the best case for an algorithm that has a linearithmic complexity?
a)
O(n log n)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(2^n)
30.
Whath is the average case for an algorithm that has a linearithmic complexity?
a)
O(n log n)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(2^n)
31.
Whath is the worst case for an algorithm that has a linearithmic complexity?
a)
O(n^2)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
32.
Which rule describes linearithmic complexity?
a)
As the number of cases doubles, the time needed stays the same
b)
As the number of cases doubles, the time needed increases by one
c)
As the number of cases doubles, the time needed doubles
d)
As the number of cases doubles, the time more than doubles (but close to linear)
33.
Which graph below has a complexity of O(n log n)?
a)
Option 1
b)
Option 2
c)
Option 3
d)
Option 4
e)
Option 5
34.
Which of the following is an example of a problem with a complexity of O(n^2)?
a)
Finding the shortest route between a series of cities by working out each route and choosing the shortest.
b)
Using quick sort to put boxes in order from lowest to highest
c)
Looking for an item using a binary search strategy (sorted items only)
d)
Retrieving a value from a list using it's index
e)
Sorting items by comparing each item with every other item (selection sort)
35.
What is the best case for an algorithm that has a quadratic complexity?
a)
O(n^2)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
36.
Whath is the average case for an algorithm that has a quadratic complexity?
a)
O(n^2)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
37.
Whath is the worst case for an algorithm that has a quadratic complexity?
a)
O(n^2)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
38.
Which rule describes quadratic complexity?
a)
As the number of cases doubles, the time needed stays the same
b)
As the number of cases doubles, the time needed increases by one
c)
As the number of cases doubles, the time needed doubles
d)
As the number of cases doubles, the time more than doubles (but close to linear)
e)
As the number of cases doubles, the time needed increases four times
39.
Which graph below has a complexity of O(n^2)?
a)
Option 1
b)
Option 2
c)
Option 3
d)
Option 4
e)
Option 5
40.
Which of the following is an example of a problem with a complexity of O(2^n)?
a)
Working out the most efficient way to fill a bag so that the value of the items is maximised
b)
Finding the shortest route between a series of cities by working out each route and choosing the shortest.
c)
Using quick sort to put boxes in order from lowest to highest
d)
Looking for an item using a binary search strategy (sorted items only)
e)
Retrieving a value from a list using it's index
41.
What is the best case for an algorithm that has a exponential complexity?
a)
O(n)
b)
O(log n)
c)
O(n log n)
d)
O(n^2)
e)
O(2^n)
42.
Whath is the average case for an algorithm that has a exponential complexity?
a)
O(2^n)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
43.
Whath is the worst case for an algorithm that has a exponential complexity?
a)
O(2^n)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
44.
Which rule describes exponential complexity?
a)
As we add one to the number of cases, the time needed doubles
b)
As the number of cases doubles, the time needed stays the same
c)
As the number of cases doubles, the time needed increases by one
d)
As the number of cases doubles, the time needed doubles
e)
As the number of cases doubles, the time more than doubles (but close to linear)
45.
Which graph below has a complexity of O(2^n)?
a)
Option 1
b)
Option 2
c)
Option 3
d)
Option 4
e)
Option 5
46.
The underlying complexity of the algorithm used to find the guaranteed shortest route is...
a)
linear
b)
log n
c)
quadratic
d)
n log n
e)
factorial
47.
What is the complexity of the travelling salesman problem?
a)
factorial O(n!)
b)
constant O(1)
c)
linear O(n)
d)
quadratic O(n^2)
e)
logarithmic O(log n)
48.
Which of the following is an example of a problem with a complexity of O(n!)?
a)
Finding the shortest route between a series of cities by working out each route and choosing the shortest.
b)
Using quick sort to put boxes in order from lowest to highest
c)
Looking for an item using a binary search strategy (sorted items only)
d)
Working out the most efficient way to fill a bag so that the value of the items is maximised
e)
Retrieving a value from a list using it's index
49.
What is the best case for an algorithm that has a factorial complexity?
a)
O(n!)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
50.
Whath is the average case for an algorithm that has a factorial complexity?
a)
O(n!)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
51.
Whath is the worst case for an algorithm that has a factorial complexity?
a)
O(n!)
b)
O(1)
c)
O(n)
d)
O(log n)
e)
O(n log n)
52.
Which graph below has a complexity of O(n!)?
a)
Option 1
b)
Option 2
c)
Option 3
d)
Option 4
e)
Option 5
53.
The graphs of O(n!) and O(2^n) look very similar. In reality which function grows at the fastest rate? You can google the answer if you are not sure.
a)
O(2^n)
b)
O(n!)
54.
Which three of our five tractable algorithms have a best case of O(1)?
a)
Constant
b)
Linear
c)
Logarithmic
d)
Linearithmic
e)
Quadratic
55.
Which of our five tractable algorithms have the same best, average and worst case?
a)
Constant
b)
Linear
c)
Logarithmic
d)
Linearithmic
e)
Quadratic
56.
Which of our two algorithms have the same worst case?
a)
Constant
b)
Linear
c)
Logarithmic
d)
Linearithmic
e)
Quadratic
57.
Which sequence below is factorial (n!)
a)
1, 2, 3, 4, ...
b)
1, 2, 4, 8, 16, 32, ...
c)
1, 4, 9, 16, 25, 36, ...
d)
1, 2, 6, 24, 120, ...
e)
1, 1, 2, 3, 5, 8, 13, 21, ...
58.
Which sequence below is exponential (2^n)
a)
1, 2, 3, 4, ...
b)
1, 2, 4, 8, 16, 32, ...
c)
1, 4, 9, 16, 25, 36, ...
d)
1, 2, 6, 24, 120, ...
e)
1, 1, 2, 3, 5, 8, 13, 21, ...
59.
Which sequence/s below have an underlying algorithm that is intractable?
a)
1, 2, 3, 4, ...
b)
1, 2, 4, 8, 16, 32, ...
c)
1, 4, 9, 16, 25, 36, ...
d)
1, 2, 6, 24, 120, ...
e)
1, 1, 2, 3, 5, 8, 13, 21, ...
100 %
