1. In essence, Big O notation tells you how fast a function grows or declines
2. Landau's symbol comes from the name of the German number theoretician Edmund
Landau who invented the notation. The letter O is used because ________________
3. Refer to the following diagram and definition. Select the option that correctly defines A, B and C
4. Fill in the blanks for the following excerpt
5. In general, how can you determine the running time of a piece of code? The answer is that it depends on what kinds of statements are used. Fill in the blanks for A, B and C
6. Read the following excerpt and see if you can fill in the blank with the most appropriate option
7. Read the following excerpt and decide which of the following statements is a natural conclusion and most accurate
8. The time required by a function/procedure is proportional to the number of "basic operations" that it performs. What is an example of a basic operation?
9. Can you fill in the blanks for the following excerpt?
11. Decide whether the following excerpt is true or false
12. Typically, we are usually interested in the _____________: what is the ___________ number of operations that might be performed for a given problem size
13. In reference to the following excerpt, in the worst case, inserting at the
beginning of the array, _________________________________________
14. For a linear-time algorithm, if the problem size doubles, the number of operations will be cut in half
15. _______describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
16. _______ describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
17. _____________ represents an algorithm whose performance is directly proportional to the square of the size of the input data set
18. ____________ denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2N) function is exponential - starting off very shallow, then rising meteorically
19. O(log n) >> Example: Finding an item in a sorted array with a ____________ or a balanced search tree as well as all operations in a Binomial heap.
20. Determining if a number is even or odd; using a constant-size lookup table would be an example of:
21. Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search would be:
22. Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
23. The loop executes N times, so the sequence of statements also executes N times. If we assume the statements are O(1), the total time for the for loop is:
24. The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of:
25.
When a statement involves a function/ procedure call, the complexity of the statement includes the complexity of the function/ procedure