# 04 - Efficiency of Algorithms

1. The importance of efficiency with respect to time was emphasised by _____________ in 1843 as applying to Charles Babbage's mechanical analytical engine

Bill Gates

John Von Neumann

Alan Turing

2. Complexity theory is interested in how algorithms scale with an increase in the input size.

FALSE

TRUE

3. The order of an algorithm is a measure of the efficiency (______________________) of the algorithm as a function of the size of the problem.

number of operations

number of outputs

number of inputs

number of loops or iterative structures used

4. An algorithm is considered efficient if its resource consumption, also known as computational cost, is at or below some acceptable level.

FALSE

TRUE

5. Roughly speaking, 'acceptable' means: it will _______________________________ on an available computer, typically as a function of the size of the input

run in a reasonable amount of time or space

fail to cause any errors

produce an exponential output

run until it halts

6. Thanks to the approximate doubling of computer power every 2 years, tasks that are acceptably efficient on modern smartphones and embedded systems may have been unacceptably inefficient for industrial servers 10 years ago

TRUE

FALSE

7. The most commonly used notation to describe resource consumption or "complexity" is Donald Knuth's __________________________

A* Algorithm

Chaos theorem

Algorithmic Analysis

Big O notation

8. For example, bubble sort may be faster than merge sort when only a few items are to be sorted; however either implementation is likely to meet performance requirements for a __________

non linear stack

small list

non existent list

large list

9. Algorithms which include ______________________ may be more difficult to analyze in terms of Big O

small data sets

parallel processing

infinite queues

more than one input

10. What is being defined here: "An upper bound on the running time for any input of given size"
```There are three factors we need to consider
for time complexity
-------------------------------------------

1. Worst case
2. Average case
3. Best case
```

Best case

Average case

None of the listed options

Worst case

11. What is being defined here: "The lower bound on the running time"

Best case

Worst case

Average case

None of the listed options

12. What is being defined here: "Assume all inputs of a given size are equally likely"

None of the listed options

Average case

Best case

Worst case

13. In the example of a sequential search of a list of size 'n', in the worst case there are __ comparisons and the best case the number of comparisons is: ___

n / 1

n / n - 2

1 / n

n / n -1

14. In the case of a sequential search of a list of size 'n', the average case would be:

n/2 comparisons

n - 1 comparisons

n comparisons

n * 2 comparisons

15. An algorithm filling a matrix of size n*m with natural numbers 1,2,……will run in ___________

O(n)

O(n*m)

O(n*m/2)

O(n/m)

16. Non polynomial algorithms will only work for very large input data sets

FALSE

TRUE

17. Select the statement that best describes the following complexity example. Runs in O(n^2) where n is the size of the array

Runs in cubic time O(n^3)

Runs in O(n) where n is the size of the array

18. Select the statement that best describes the following complexity example. Runs in O(n^2) where n is the size of the array

Runs in O(n) where n is the size of the array

Runs in cubic time O(n^3)

19. Select the statement that best describes the following complexity example. Runs in O(n^2) where n is the size of the array

Runs in cubic time O(n^3)

Runs in O(n) where n is the size of the array

20. Select the statement that best describes the following complexity example. Runs in O(n) where n is the size of the array

Runs in cubic time O(n^3)

Runs in O(n^2) where n is the size of the array

21. The following runs in exponential time >> O(2^n) TRUE

FALSE

22. The following runs in linear time O(n) FALSE

TRUE

23. For the following data structures and actions, can you fill in the blanks for A, B and C A, B, C = O(1)

A,B,C = O(n)

A = O(1); B = O(n); C=O(1)

A = O(1); B,C = O(n)

24. The Big O notation for a hash table (adding a value) e.g. Dictionary would be O(n)

FALSE

TRUE

25. Out of all the data structures the 'hash table' is generally considered the slowest for all the typical 'add', 'delete' and 'find' operations. O(n^3)

FALSE

TRUE