Comparing and evaluating algorithms

9.What does run-time analysis estimate?

10.Binary search on a sorted list of size n runs in a number of steps proportional to the square of n.

11.Which of the following best describes the 'hidden constant' in asymptotic analysis?

12.Why might counting an addition of two numbers as one step be unwarranted in some contexts?

13.What does the term 'space complexity' refer to?

14.The term 'analysis of algorithms' was coined by Alan Turing.

15.Which of the following notations is used to estimate complexity in the asymptotic sense?

16.Match each cost model to its description.

17.Order the following steps in the typical process of analysing an algorithm's run-time:

18.Match each algorithm to its typical time complexity (in Big O notation) for a list of size n.

19.Arrange the following steps in the correct order for comparing two algorithms using logical reasoning.

20.Which of the following are advantages of using logical reasoning (theoretical analysis) to compare algorithms, rather than just benchmarking them? (select all that apply)

21.An algorithm with a time complexity of O(n²) will always be slower than one with O(n) for the same input size.

22.The term 'analysis of algorithms' was coined by:

23.Which of the following are reasons why empirical benchmarking alone is insufficient to compare algorithm efficiency? (select all that apply)

24.Which algorithm has a time complexity of O(log n)?

25.For a list of 1000 elements, binary search will always be faster than linear search.

26.A student writes two programs to search a sorted list of 1000 names. Program 1 uses linear search and Program 2 uses binary search. Both are run on the same computer. Which statement is correct?

27.A programmer compares two algorithms for the same problem by running them on a fast computer and a slow computer. The fast computer runs Algorithm A, the slow computer runs Algorithm B. For a small input size, Algorithm A appears much faster. What is the most likely reason this conclusion may be wrong?

28.Consider two algorithms for the same problem. Algorithm X has time complexity O(n) and Algorithm Y has time complexity O(n²). On a particular input of size 100, Algorithm X takes 10 ms and Algorithm Y takes 5 ms. What can you conclude?

29.A student measures the run-time of a sorting algorithm on lists of sizes 100, 200, 400, and 800, obtaining times of 1 ms, 4 ms, 16 ms, and 64 ms respectively. Which of the following statements are true? (select all that apply)

30.In the uniform cost model, the cost of an addition operation is proportional to the number of bits in the numbers being added.

31.Match each algorithm to its typical time complexity for a list of size n.

32.Arrange the following steps in the correct order for comparing two algorithms using logical reasoning (theoretical analysis).

33.An algorithm processes a list of n numbers. On a particular computer, the run-time T(n) is measured and found to fit the equation T(n) = 0.001n² + 3n milliseconds. What is the dominant term for very large values of n, and what is the time complexity in Big O notation?

34.A student wants to compare the efficiency of two algorithms for the same problem. Which of the following is the most reliable method to compare them across different computers?

35.Two algorithms, A and B, solve the same problem. Algorithm A has time complexity O(n) and Algorithm B has time complexity O(log n). On a particular computer, Algorithm A takes 1 second for an input of size 1000. Approximately how long would Algorithm A take for an input of size 2000, assuming the constant factor remains the same?

36.A student measures the run-time of a sorting algorithm on lists of sizes 100, 200, 400, and 800, obtaining times of 1 ms, 4 ms, 16 ms, and 64 ms respectively. What is the likely time complexity of the algorithm?

37.Which of the following are advantages of using logical reasoning (theoretical analysis) over empirical benchmarking when comparing algorithms? (select all that apply)

38.In the logarithmic cost model, the cost of an addition operation is proportional to the number of bits in the numbers being added.

39.Match each cost model to its correct description.

40.Arrange the following steps in the correct order for using logical reasoning to compare two algorithms for the same problem.

41.Fill in the blanks with the correct terms.

42.Fill in the blank with the correct notation.

43.What are the three types of case descriptions that may be of interest when analysing an algorithm?

44.Fill in the blank with the correct term.

45.What is the maximum number of time units needed for binary search on a sorted list of n elements if each lookup takes unit time?

46.What does the 'space complexity' of an algorithm measure?

47.If a binary search on a sorted list of n elements takes at most log2(n) + 1 time units, what is the maximum number of time units needed for a list of 8 elements?

48.Fill in the blank: The number of steps for binary search is proportional to the ___ of the list size n.

49.A binary search algorithm on a sorted list of n elements takes at most log₂(n) + 1 time units. What is the maximum number of time units needed for a list of 16 elements?

50.Complete the sentence.

51.A company benchmarks two sorting algorithms on the same data set. For a list of 10,000 items, Algorithm A takes 0.5 seconds and Algorithm B takes 2 seconds. However, theoretical analysis shows that Algorithm A is O(n²) and Algorithm B is O(n log n). Explain why the benchmark result might be misleading, and predict what would happen if the list size were increased to 1,000,000 items.

52.Using the uniform cost model, how many steps does it take to perform 5 additions of two numbers, if each addition is counted as one step?

53.Explain why empirical benchmarking alone is not sufficient to compare the efficiency of algorithms, using the example of linear search on a fast computer versus binary search on a slow computer.

54.Explain why counting an addition of two numbers as one step might not be a valid assumption in all contexts.

55.If a binary search on a sorted list of n elements takes at most log2(n) + 1 time units, what is the maximum number of time units needed for a list of 8 elements?

56.A binary search algorithm on a sorted list of n elements takes at most log₂(n) + 1 time units. What is the maximum number of time units needed for a list of 16 elements?

57.Using the uniform cost model, how many steps does it take to perform 5 additions of two numbers, if each addition is counted as one step?