# 12 - Efficiency of Algorithms Basics

1. All algorithms are exactly the same in terms of their efficiency in solving the same problem (e.g. binary and linear search)

FALSE

TRUE

2. Measures are normally expressed as a function of the size of the input n. Common measures include:

All of the above

Space: How much working memory (RAM) is needed by the algorithm?

Space: How much memory is needed by the code and the amount of memory needed for the data on which the code operates

Time: how long does the algorithm take to complete?

3. On a very small list of say two items, it would be more efficient to use the following searching algorithm:

linear search

binary search

bubble search

merge sort

4. If an application is time critical then it may be better to prioritise speed over space

FALSE

TRUE

5. A certain program requires the value of every pixel in a stored image to be changed. There are two algorithms available. What statement is true of algorithm #1
```Algorithm #1
=============
1. Entire image (all pixels) is read into memory
2. A parallel calculation is applied on every pixel
3. The image is then stored /saved again.

Algorithm #2
=============
1. A single pixel is read into memory
2. A calculation isperformed on the single pixel
3. The pixel (which has been changed) is stored.
4. REPEAT all the above steps until all the pixels are dealt with. ```

None of the above

Algorithm #1 is very fast and also space efficient as next to no memory is necessary

Algorithm #1 is very slow but needs only minimal memory to store the image

Algorithm #1 is very fast but needs enough memory in order to hold the entire image and perform the calculation.

6. For maximum algorithm efficiency we wish to minimize resource usage (the resources being …..)

time and space

lists and loops

stacks and queues

CPU usage and list memory

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

Grace Hopper

Bill Gates

Alan Turing

8. Often a task could be handled either by using a fast algorithm which used a lot of memory, or by using a slower algorithm which used very little working memory

This is called the 'impossible problem of Computing'

None of the above

This is called a space-time trade off

This is called the space-divide

9. An algorithm is considered efficient if its resource consumption (or computational cost) is at or below some acceptable level. Roughly speaking, 'acceptable' means:

it will take a very long time to process such that the length is equal to the time

it will run an infinite loop ensuring that the solution will be eventually found

it will take a very short amount of time and the absolute minimum resources

it will run in a reasonable amount of time on an available computer

10. Big O notation is used to represent the complexity of an algorithm as a function of the size of the input n

TRUE

FALSE

11. One factor in efficiency is called 'scalability' or complexity. In this context, complexity means 'if input n increases, how much longer does it take to complete' which is…

coarse complexity

bubble complexity

time complexity

space complexity

12. The question:" If input 'n' increases how many more resources does it need" is essentially referring to 'space complexity'.

FALSE

TRUE

13. For the following algorithm, which sums up all the numbers up to 'n', the time taken to complete this algorithm ……
```For x = 1 to n
x = x + 1
Next x

#Note this is more like VB.Net code than Python```

is directly related to the size of n

All of the above are correct

In this case time is said to increase 'linearly' with n

if n was 2000, it would take 2000 loops to complete

14. It is preferrable to have an algorithm which is constant and does not depend on the size of n.
`And the following algorithm is an improvement on using a for loop to sum up all the numbers up to 'n'. Sum of numbers = n(n+1) / 2`

TRUE

FALSE

15. Suppose you were required to sort 200 words into alphabetical order. You could do this using brute force going through every combination to find the right order.

In mathematical terminology the number of combinations in this case would be factorial 200 or 200!

Even with a powerful computer, it would still take an incredibly long (impossibly long) time to work out.

All of the above statements are true.

The time efficiency of this algorithm is factorial n (n!)

16. The more practical way to attempt a sort would be to use a

lineary or binary search

None of the above

bubble or quick sort

faster CPU to compute the factorial

17. Is it better to run a really fast algorithm that takes up a lot of memory or is it better to run a slower algorithm that uses less memory?

It is always better to have a fast algorithm

None of the above

It depends on whether the desired output is time critical or if there is a hardware limit

It is always better to have a slower algorithm which takes less space

18. If there is a hardware limit to the memory capacity then a slower algorithm may be best for the situation

TRUE

FALSE

19. Look at the two algorithms that require the value of every pixel in a stored image to be changed. What is true of algorithm #2?
```Algorithm #1
=============
1. Entire image (all pixels) is read into memory
2. A parallel calculation is applied on every pixel
3. The image is then stored /saved again.

Algorithm #2
=============
1. A single pixel is read into memory
2. A calculation isperformed on the single pixel
3. The pixel (which has been changed) is stored.
4. REPEAT all the above steps until all the pixels are dealt with. ```

Algorithm #2 is slower than Algorithm #1 but the memory requirement is minimal as compared to Algorithm #1

Algorithm #2 is much faster than the first algorithm and the memory requirement is also minimal

Algorithm #2 is clearly the superior algorithm in terms of both speed and space efficiency

Algorithm #2 is much slower than #1 and also has a huge memory and space requirement

20. The Big O notation (learn more in advanced levels) basically quantifies how the input 'n' affects the outcome O

TRUE

FALSE