MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

Python · A Level 8

Big-O and Algorithm Complexity

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 20 marks. Total 30 marks.

Name

Class

Date

Mark  / 30

Section A

Circle the letter of the correct answer. One mark each.

  1. 1What does Big-O notation describe?1
    1. AThe amount of memory a computer has available
    2. BHow the cost of an algorithm grows as the size of the input grows
    3. CThe exact time an algorithm takes in seconds
    4. DThe number of lines of code in an algorithm
  2. 2What is the time complexity of reading items[5] from a list?1
    1. AO(1)
    2. BO(log n)
    3. CO(n)
    4. DO(n squared)
  3. 3What is the worst case time complexity of a binary search?1
    1. AO(n log n)
    2. BO(1)
    3. CO(log n)
    4. DO(n)
  4. 4A function has one loop that runs n times, and inside it another loop that runs n times. What is its complexity?1
    1. AO(log n)
    2. BO(n)
    3. CO(2n)
    4. DO(n squared)
  5. 5What is the complexity of an algorithm that takes 5n + 20 steps?1
    1. AO(5n)
    2. BO(n)
    3. CO(20)
    4. DO(n + 20)
  6. 6Which of these growth rates is the worst for a large input?1
    1. AO(2 to the power n)
    2. BO(n)
    3. CO(n log n)
    4. DO(n squared)
  7. 7What is the average time complexity of merge sort?1
    1. AO(n log n)
    2. BO(log n)
    3. CO(n squared)
    4. DO(n)
  8. 8If an O(n) algorithm takes 2 seconds for an input of size n, roughly how long does it take for 2n?1
    1. A8 seconds
    2. B16 seconds
    3. C4 seconds
    4. D2 seconds
  9. 9What does space complexity measure?1
    1. AThe amount of space that the program's code takes up when it is stored on a disk
    2. BHow many variables have been given names in the source code of the program
    3. CHow many steps the algorithm takes as the size of the input grows
    4. DHow the amount of memory needed grows as the size of the input grows
  10. 10What is an intractable problem?1
    1. AOne that needs more than one programmer
    2. BOne that no algorithm can ever solve
    3. COne where the only known algorithms take exponential time, so only small cases can be solved
    4. DOne that is solved in polynomial time but takes a long time to code

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1StateState what is meant by Big-O notation.2
  2. 2StateState the time complexity, using Big-O notation, of each of the following. (a) Reading an item from an array when its index is known. (b) A linear search of a list of n items. (c) A binary search of a sorted list of n items. (d) A bubble sort of n items, in the worst case.4
  3. 3StateThe subprogram shown is called with a list of n items. State its time complexity, and explain how you decided.4
    Python
    def mystery(items):
    count = 0
    for a in items:
        for b in items:
            if a == b:
                count += 1
    return count
  4. 4ExplainExplain what is meant by an intractable problem, and describe one way in which programmers deal with such problems.4
  5. 5CompareTwo subprograms check whether a list of n items contains a duplicate. The first compares every pair of items. The second adds each item to a set as it goes, and stops if an item is already in the set. Compare the two subprograms in terms of time and space complexity.6

Mark scheme

Section A

1B2A3C4D5B6A7A8C9D10C

Section B

1 State what is meant by Big-O notation. 2

One mark for each of the following, to a maximum of 2.

  • It describes how the time or memory an algorithm needs grows as the size of the input grows
  • It ignores constants and gives an upper bound, usually the worst case

Model answer. Big-O notation describes how the time, or the memory, that an algorithm needs grows as the size of its input grows. It ignores constant factors and smaller terms and gives an upper bound, which is usually the worst case.

2 State the time complexity, using Big-O notation, of each of the following. (a) Reading an item from an array when its index is known. (b) A linear search of a list of n items. (c) A binary search of a sorted list of n items. (d) A bubble sort of n items, in the worst case. 4

One mark for each of the following, to a maximum of 4.

  • (a) O(1)
  • (b) O(n)
  • (c) O(log n)
  • (d) O(n squared)

Model answer. (a) O(1), constant time, because the position is calculated directly. (b) O(n), linear, because in the worst case every item is checked. (c) O(log n), logarithmic, because each comparison halves the items that remain. (d) O(n squared), quadratic, because there is a pass of up to n comparisons for each of up to n passes.

3 The subprogram shown is called with a list of n items. State its time complexity, and explain how you decided. 4

One mark for each of the following, to a maximum of 4.

  • The time complexity is O(n squared)
  • There is a loop inside another loop
  • Both loops go through all n items
  • So the inner loop runs n times for each of the n passes of the outer loop, a total of n times n steps

Model answer. The time complexity is O(n squared). The subprogram contains one loop nested inside another, and both loops go through all n items. The inner loop runs n times for each of the n passes of the outer loop, so the total number of steps is n times n. This means that doubling the length of the list would make it take about four times as long.

4 Explain what is meant by an intractable problem, and describe one way in which programmers deal with such problems. 4

One mark for each of the following, to a maximum of 4.

  • A problem for which the only known algorithms take exponential time, or worse
  • The time needed grows so quickly that only small inputs can be solved in a reasonable time
  • A heuristic can be used instead
  • It finds a good, but not necessarily the best, solution in a reasonable time

Model answer. An intractable problem is one for which the only known algorithms take exponential time or worse, so the time needed grows so quickly with the size of the input that only small cases can be solved in a reasonable time, however fast the computer. A programmer can use a heuristic instead, which is a rule of thumb that finds a good solution, though not necessarily the best one, in a reasonable time. For the travelling salesman problem, always travelling to the nearest unvisited city is an example.

5 Two subprograms check whether a list of n items contains a duplicate. The first compares every pair of items. The second adds each item to a set as it goes, and stops if an item is already in the set. Compare the two subprograms in terms of time and space complexity. 6

One mark for each of the following, to a maximum of 6.

  • The first compares every pair, so takes O(n squared) time
  • The second looks at each item once, so takes O(n) time
  • Checking whether an item is in a set takes constant time on average, which is what makes the second one fast
  • The first needs almost no extra memory, O(1) space
  • The second needs a set that could hold every item, O(n) space
  • A conclusion: the second is better for a long list because the time saved outweighs the memory, though the first could suit a very small or a memory limited device

Model answer. The first subprogram compares every pair of items, so it takes O(n squared) time, but it needs almost no extra memory, O(1) space. The second looks at each item once, so it takes O(n) time, because checking whether an item is in a set takes constant time on average. However, the set may end up holding every item, so it needs O(n) space. The second is the better choice for a long list, because the saving in time is enormous and outweighs the cost in memory. The first could still suit a very short list, or a device with very little memory, where the extra memory is the greater concern.