1. The importance of efficiency with respect to time was emphasised by _____________ in 1843 as applying to Charles Babbage's mechanical analytical engine
2. Complexity theory is interested in how algorithms scale with an increase in the input size.
3. The order of an algorithm is a measure of the efficiency (______________________) of the algorithm as a function of the size of the problem.
4. An algorithm is considered efficient if its resource consumption, also known as computational cost, is at or below some acceptable level.
5. Roughly speaking, 'acceptable' means: it will _______________________________ on an available computer, typically as a function of the size of the input
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
7. The most commonly used notation to describe resource consumption or "complexity" is Donald Knuth's __________________________
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 __________
9. Algorithms which include ______________________ may be more difficult to analyze in terms of Big O
10. What is being defined here: "An upper bound on the running time for any input of given size"
11. What is being defined here: "The lower bound on the running time"
12. What is being defined here: "Assume all inputs of a given size are equally likely"
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: ___
14. In the case of a sequential search of a list of size 'n', the average case would be:
15. An algorithm filling a matrix of size n*m with natural numbers 1,2,……will run in ___________
16. Non polynomial algorithms will only work for very large input data sets
17. Select the statement that best describes the following complexity example.
18. Select the statement that best describes the following complexity example.
19. Select the statement that best describes the following complexity example.
20. Select the statement that best describes the following complexity example.
21. The following runs in exponential time >> O(2^n)
22. The following runs in linear time O(n)
23. For the following data structures and actions, can you fill in the blanks for A, B and C
24. The Big O notation for a hash table (adding a value) e.g. Dictionary would be O(n)
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)
