06 - Past Paper Simulation - Big O(A)

 1. Explain what the term 'time complexity' means, with reference to the options below and their Big O time complexity. (3 marks)
Jesse is leading an artificial intelligence team on 
creating a simulation for an adventure playground. 

Two options have been put forward by some programmers
that present different solutions to one part of the 

The table below shows the Big O time complexity for each solution, where n = the number of data item.

Use 'data size' as a reference in your answer.

 2. Refer to Question 1's table. Name the space complexity for each solution (Option 1 and Option 2) (2 marks)

 3. Explain, with reference to the Big O complexities of option 1 and option 2, which solution you would suggest Jesse chooses (2 marks)

 4. James is aware that the recursive function has the Big O notation of O(n). State the purpose of Big O notation. (1 mark)
James wishes to create an online sensation
which will replicate the creation of popular
2 player board games.

He will be using a 2d array to simulate the board
as well as a particular recursive function.

 5. Joel has invented a game and proposed it to James, the details of which are in the excerpt. If a recursive function was used in this case explain what the Big O notation O(n) means for this function (1 mark)
It uses a 6-sided dice and moving that number of spaces. 
Both players start on the START space. If a player lands on a space occupied by the other player, they move to the next available space

 6. Read the excerpt below and state the complexity of searching the pets in Big-O notation.(1 mark)
Oliver, obsessed by his video games and cats, 
is creating a video game that stars cats.

He has decided to store the number of cats a 
player has in a 1-dimensional array. 

At each timer interval, the array is searched, 
using a linear search, to check if any cats'
appetite or health values are greater than 90%. 

If they are, an alert is displayed to the player.

 7. A given computer takes 4 milliseconds (ms) to search an array of 20 cats. Calculate an estimate of how long the computer will take to search an array of 100 pets. Show your working (1 marks)

 8. A given computer takes 8 milliseconds (ms) to solve a 3 disk problem. Calculate how long the computer takes to solve a 5 disk problem. (1 mark)
Brilliant computing genius Winston has worked out
that the complexity of solving the Towers of 
Hanoi can be expressed in Big O notation as O(2n)
where n is the number of disks.

 9. State one reason why the answer given for question 8 may only be an estimate. (1 mark)

 10. What does the graph below show? What type of graph/curve is it? (2 marks)

 11. Read the excerpt below and name the term it is referring to (fill in the blanks). (1 mark)
The performance of multiple calculations at the same
 time on a computer system. The calculations can be
 separated by using two separate processors, one 
processor with additional cores, or by using 
different threads on the processor. The calculations
 may or may not interact with one another at some 
point in the process.

Many developers think “______________" and parallelism means 
executing at the same time” which is along the right lines,
but with one big difference: ____________ gives you a 
feel of parallelism and parallelism as the name implies 
is actual parallelism.

 12. This function runs in _____time (or _______) relative to its input. The input list could be 1 item or 1,000 items, but this function would still just require one step. (1 mark)
def print_first_item(items):
    print items[0]

 13. This function runs in ______ time (or ________, where n is the number of items in the list. If the list has 10 items, we have to print 10 times. If it has 1,000 items, we have to print 1,000 times. (1 mark)
def print_all_items(items):
    for item in items:
        print item

 14. This function runs in quadratic time. If the list has ten items, how many times would you have to print it? Write your answer using the word, not the numeric representation of the number e.g. four hundred(1 mark)
  def print_all_possible_ordered_pairs(items):
    for first_item in items:
        for second_item in items:
            print first_item, second_item

 15. When using Big O notation you can 'throw out' the constants. In this example which is O(2n) we can just simplify it to:
def print_all_items_twice(items):
    for item in items:
        print item

    # Once more, with feeling
    for item in items:
        print item