1. Which of the following Big O notations is appropriate for the complexity of a search algorithm?
a. O(n2)
b. O(1)
c. O(logn)
d. O(n)
2. Which of the following Big O notations is appropriate for the complexity of a sort algorithm?
a. O(n)
b. O(1)
c. O(logn)
d. O(n2)
3. Which of the following algorithms will run in constant time?
a. accessing an element of an array
b. traversing an array
c. binary search on a sorted array
d. sorting an array
4. What is the evaluation of an algorithm’s performance and efficiency known as?
a. hash table
b. basic operations
c. solution costs
d. asymptomatic analysis
5. Which of these matches keys to values and stores and stores them?
a. simple data structure
b. hash table
c. efficiency
d. unsorted array
Answers:
1. d. O(n)
2. d. O(n2)
3. a. accessing an element of an array
4. d. asymptotic analysis
5. b. hash table
1. The appropriate Big O notation for the complexity of a search algorithm is:
d. O(n) - This notation implies that the time complexity of the algorithm is proportional to the size of the input.
2. The appropriate Big O notation for the complexity of a sort algorithm is:
d. O(n^2) - This notation implies that the time complexity of the algorithm is proportional to the square of the size of the input.
3. The algorithm that will run in constant time is:
a. accessing an element of an array - Accessing an element of an array is a constant time operation as it does not depend on the size of the array.
4. The evaluation of an algorithm's performance and efficiency is known as:
d. asymptomatic analysis - Asymptotic analysis involves analyzing an algorithm's performance as the input size approaches infinity.
5. The data structure that matches keys to values and stores them is:
b. hash table - A hash table is a data structure that provides key-value mappings and stores them using a hash function.
1. To determine the appropriate Big O notation for the complexity of a search algorithm, you need to consider how the algorithm's runtime grows as the input size increases.
- Option a (O(n^2)) represents a quadratic complexity, which means the algorithm's runtime grows exponentially with the input size. This is not suitable for a search algorithm.
- Option b (O(1)) represents constant complexity, indicating that the runtime does not depend on the input size. This is not typically achievable for a general search algorithm.
- Option c (O(logn)) represents logarithmic complexity, where the runtime grows slowly as the input size increases. This is a good fit for search algorithms like binary search, which divide the search space in half at each step.
- Option d (O(n)) represents linear complexity, meaning that the runtime grows linearly with the input size. This is suitable for sequential search algorithms.
Therefore, for a search algorithm, the appropriate Big O notation would be c. O(logn) or d. O(n), depending on the specific algorithm.
2. To determine the appropriate Big O notation for the complexity of a sort algorithm, you need to consider how the algorithm's runtime grows as the input size increases.
- Option a (O(n)) represents linear complexity, where the runtime grows linearly with the input size. This is typically not achievable for general-purpose sort algorithms.
- Option b (O(1)) represents constant complexity, indicating that the runtime does not depend on the input size. This is not suitable for a sort algorithm that needs to process the entire input.
- Option c (O(logn)) represents logarithmic complexity, where the runtime grows slowly as the input size increases. This is not suitable for sort algorithms as they usually have a higher complexity.
- Option d (O(n^2)) represents quadratic complexity, where the runtime grows exponentially with the input size. This is a common complexity for sorting algorithms like bubble sort and selection sort.
Therefore, for a sort algorithm, the appropriate Big O notation would be d. O(n^2).
3. To determine which algorithm will run in constant time, you need to understand that constant time means that the runtime remains the same, regardless of the input size.
- Option a (accessing an element of an array) runs in constant time because accessing an element at a particular index in an array takes the same amount of time, regardless of the array size.
- Option b (traversing an array) runs in linear time, as it needs to visit each element in the array.
- Option c (binary search on a sorted array) runs in logarithmic time, not constant time. It halves the search space at each step, resulting in a runtime proportional to log(n), where n is the size of the array.
- Option d (sorting an array) does not run in constant time. Sorting algorithms generally have complexities higher than constant time.
Therefore, the algorithm that runs in constant time is a. accessing an element of an array.
4. The evaluation of an algorithm's performance and efficiency is known as asymptotic analysis.
- Option a (hash table) is a data structure used for efficient key-value storage and retrieval, not specifically related to evaluating algorithm performance.
- Option b (basic operations) refers to the specific actions performed by an algorithm but not the evaluation of its performance.
- Option c (solution costs) does not specifically capture the evaluation of an algorithm's performance and efficiency.
- Option d (asymptotic analysis) is the correct choice as it refers to the process of analyzing the performance of an algorithm as the input size grows towards infinity. It helps identify the dominant factors that impact the algorithm's runtime and memory usage.
Therefore, the evaluation of an algorithm's performance and efficiency is known as d. asymptotic analysis.
5. The data structure that matches keys to values and stores them is a hash table.
- Option a (simple data structure) is a general term that does not specifically refer to matching keys to values.
- Option b (hash table) is the correct choice as hash tables are specifically designed to store and retrieve values based on keys efficiently using a hashing function.
- Option c (efficiency) is a general term and does not represent a specific data structure.
- Option d (unsorted array) is a basic data structure but does not have inherent key-value matching and storage capabilities like a hash table.
Therefore, the correct choice is b. hash table.