- The Efficiency Of Algorithms Test Bank Ch4

Chapter 4 - The Efficiency of Algorithms

True/False (13)

1. Time complexity is typically more important than space complexity
2. An inverse relationship often exists between the time complexity and space complexity of an algorithm.
3. Reformulating an algorithm to run faster most likely has no effect on the space requirements.
4. You cannot compute the actual time requirement of an algorithm.
5. You cannot predict the behavior of an algorithm without implementing it and timing the code.
6. In algorithm analysis, the general behavior of the algorithm is more important than the exact count of operations.
7. An algorithm’s basic operation is always the most frequent operation performed.
8. Ignoring operations that are not basic will not affect the final conclusion about algorithm speed.
9. For large values of n, the grown rate of n² is smaller than n log n.
10. For large values of n, the growth rate of n! is larger than 2ⁿ
11. The behavior of a logarithmic function is the same regardless of its base.
12. You want the upper bound on f(n) to be a large as possible.
13. All of the operations for the fixed-size array-based bag ADT have the same Big-O time complexity as the linked-based bag ADT.

Short Answer (5)

1. Order the following growth rates from smallest to largest.
   n² n! n log n 2ⁿ n log n
2. If you have a O(log n) algorithm running, what happens when you double the size of your problem?
3. What is the Big-O time complexity for an algorithm to display the n^th integer in an array of integers?
4. What is the Big-O time complexity for an algorithm to display the n^th integer in a linked chain of integers?
5. Given f(n) = 4n + 63 + 5n² + 3n log n what is g(n)?

Multiple Choice (31) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. When you write a program for an algorithm and it is taking much longer than expected you should
   1. try to design a better algorithm
   2. buy a faster computer
   3. rewrite the algorithm in a different language
   4. ignore the problem
2. A program’s execution time depends in part on
   1. the speed of the computer it is running on
   2. the memory capacity
   3. the language the algorithm is written in
   4. all of the above
3. An algorithm has
   1. time requirements
   2. space requirements
   3. both a & b
   4. none of the above
4. The memory required to run an algorithm is called
   1. space complexity
   2. memory complexity
   3. time complexity
   4. storage complexity
5. A measure of an algorithm’s execution needs is called
   1. time complexity
   2. speed complexity
   3. space complexity
   4. run time complexity
6. A “best” solution is a function of
   1. execution time
   2. space consumption
   3. programming effort
   4. all of the above
7. You should express the complexity of an algorithm in terms of it
   1. problem size
   2. space requirements
   3. execution time
   4. overall complexity
8. Problem size is defined as
   1. the number of items an algorithms processes
   2. the amount of memory an algorithms uses
   3. the amount of execution time an algorithm takes
   4. none of the above
9. Measuring the growth of an algorithm’s time requirement grows as the problem size increases is called the
   1. growth rate function
   2. time complexity
   3. space complexity
   4. overall measurement function
10. To measure the time requirement of an algorithm, we must
    1. find an appropriate growth rate function
    2. run the algorithm for different problem sizes
    3. code the algorithm in several different languages and compare the run times
    4. all of the above
11. The most significant contributor to an algorithm’s time requirement is
    1. the algorithm’s basic operation
    2. the addition operation
    3. the multiplication operation
    4. memory access time
12. Which of the following operations could be identified as the basic operation of an algorithm?
    1. addition
    2. multiplication
    3. division
    4. all of the above
13. Which one of the following would not be considered to be a basic operation?
    1. variable initialization
    2. simple assignment
    3. operations to control loop execution
    4. all of the above
14. For large values of n which statement is true?
    1. 2n³ + 4n² + 17n behaves like n³
    2. 2n³ + 4n² behaves like n³
    3. 2n³ behaves like n³
    4. all of the above
15. For large values of n which statement is true?
    1. (n² + n ) / 2 behaves like n²
    2. (n² + n ) / 2 behaves like n
    3. (n² + n ) / 2 behaves like n/2
    4. all of the above
16. Computing the sum of the first n integers using the formula n (n + 1) / 2 has a growth rate
    1. independent of n
    2. of n²
    3. of n² + n
    4. all of the above
17. To properly evaluate the effectiveness of an algorithm, you need to determine
    1. the average case
    2. the best case
    3. the worst case
    4. all of the above
18. When search an array for a particular value, which case is most useful?
    1. the average case
    2. the best case
    3. the worst case
    4. none of the above
19. If an algorithm requires 7 basic operations for an algorithm with a problem size of n, the algorithmic complexity is
    1. O(1)
    2. O(7)
    3. O(n)
    4. O(7n)
20. Given f(n) = 5n³ + 3n² + 4n + 6 what is g(n)?
    1. g(n) = (n³)
    2. g(n) = (5n³)
    3. g(n) = (5n³ + 3n²)
    4. g(n) = (n3 + n2)
21. What is the time complexity of the following if statement?
    if (condition)
    S1
    else
    S2
    1. the complexity of the condition plus the larger of the complexity of S₁ or S₂
    2. the complexity of the condition
    3. the larger of the complexity of S₁ or S₂
    4. the complexity of the condition plus the complexity of S1 and the complexity of S2
       
22. The effect of doubling the input size on an algorithm with time complexity O(n³) is
    1. 8 times
    2. 3 times
    3. double
    4. negligible
23. The effect of doubling the input size on an algorithm with time complexity O(log n) is
    1. negligible
    2. 2 log n
    3. double
    4. there is no effect
24. What is the time complexity for adding an entry to a fixed-size array-based bag ADT?
    1. O(1)
    2. O(n)
    3. O(n²)
    4. negligible
25. What is the best-case time complexity for searching a fixed-size array-based bag ADT for a particular entry?
    1. O(1)
    2. O(n)
    3. O(n²)
    4. negligible
26. What is the worst-case time complexity for searching a fixed-size array-based bag ADT for a particular entry?
    1. O(n)
    2. O(1)
    3. O(n²)
    4. negligible
27. What is the average-case time complexity for searching a fixed-size array-based bag ADT for a particular entry?
    1. O(n)
    2. O(1)
    3. O(n²)
    4. negligible
28. What is the time complexity for adding an entry to a linked-based bag ADT?
    1. O(1)
    2. O(n)
    3. O(n²)
    4. negligible
29. What is the best-case time complexity for searching a linked-based bag ADT for a particular entry?
    1. O(1)
    2. O(n)
    3. O(n²)
    4. negligible
30. What is the worst-case time complexity for searching a linked-based bag ADT for a particular entry?
    1. O(n)
    2. O(1)
    3. O(n²)
    4. negligible
31. What is the average-case time complexity for searching a linked-based bag ADT for a particular entry?
    1. O(n)
    2. O(1)
    3. O(n²)
    4. negligible