Chapter 16 Exam Review

What does a "Big O" function tell you?

• The approximate efficiency of an algorithm, given the size of the input data set

• The exact run-time of an algorithm, given a specific input data set

• The number of MB of RAM a specific input data set will consume

• The number of correct answers an algorithm will produce for an input data set

Given the following information, what can we conclude about algorithm 1 and algorithm 2? Algorithm 1: O(5) = 10 Algorithm 2: O(5) = 100

• Algorithm 1 will always complete in 10 seconds and Algorithm 2 will always complete in 100 seconds

• Algorithm 2 should be more efficient when processing 5 input elements

• Algorithm 1 should be more efficient when processing 5 input elements

• Algorithm 1, given 10 input elements, will run in the same time as Algorithm 2, given 100 input elements

If I do a linear search(O(n)) of a list of 100 items, how many possible times will the search have to execute?

• 7

• 50

• 25

• 100

If I do a binary search (O(log2n) ) of a list of 100 items, how many possible times will the search have to execute?

• 7

• 50

• 100

• 23

How can an algorithm's efficiency be measured?

• Memory

• CPU

• Time

• All of these are true

Given these algorithmic efficiencies, which of these run in an unreasonable amount of time?

• O(n)

• O(2n)

• O(n2)

Given the following efficiency reports for the first five results, which algorithms run in an unreasonable amount of time, given an input of "n" elements?

• 1 & 2

• 2 & 3

• 1 & 3

• 1, 2, & 3

Which of the following is true?

• Many algorithms can be solved in a reasonable amount of time, but some are undecidable and cannot be solved for all inputs.

• All problems can be solved with algorithms.

• Many algorithms are undecidable and can only be solved in an unreasonable amount of time.

• Many algorithms can be solved in an unreasonable amount of time, but some can be solved in a reasonable amount of time and require heuristics.

If I were to create an algorithm that found the second item in a list of n items, what could be said about this algorithm?

• The algorithm is decidable and will run in a reasonable time.

• The algorithm is undecidable and will run in an unreasonable time.

• The algorithm is undecidable and will run in a reasonable time.

• The algorithm is decidable and will run in an unreasonable time.

What does it mean for an algorithm to be undecidable?

• The algorithm has a perfect solution but it will take a while to find it

• Not everyone can agree to the solution of the problem

• There is no correct solution for every instance of the problem

• Not even a heuristic can help give you a reasonable answer