Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
Consider an arbitrary resizable array that uses expansion factor of 2.0. Which of the following statements are true? The number of elements in the resizable array is denoted by n and the capacity of the underlying low-level array by c. Random access, meaning reading or writing the ith element, takes constant time. O Adding a new element in the beginning takes amortized constant time. O Adding a new element at the end takes amortized constant time. If the initial capacity of an empty resizable array is 2 and then 5 elements are inserted at the end, the resulting capacity is 8. Finding the smallest element takes linear time (n) in the worst-case. O Finding the largest element takes logarithmic time O(log n) in the worst-case. Consider a mutable linked list, implemented so that references to the first and the last element are maintained. Which of the following statements are true? As usual, the length of the list is denoted by n. Random access, meaning reading or writing the ith element, takes constant time. O Mutable stacks can be easily implemented with mutable linked lists. Adding a new element at the end of the list can be done in constant time. □ If each list entry also has a reference to the previous entry, then removing the last element from the list can be done in constant time. The smallest element is always in the beginning of the list and thus finding the smallest element of the list can be done in constant time. O Finding the largest element in the list takes linear time in the worst-case.

Consider an arbitrary resizable array that uses expansion factor of 2.0. Which of the following statements are true? The number of elements in the resizable array is denoted by n and the capacity of the underlying low-level array by c. Random access, meaning reading or writing the ith element, takes constant time. O Adding a new element in the beginning takes amortized constant time. O Adding a new element at the end takes amortized constant time. If the initial capacity of an empty resizable array is 2 and then 5 elements are inserted at the end, the resulting capacity is 8. Finding the smallest element takes linear time (n) in the worst-case. O Finding the largest element takes logarithmic time O(log n) in the worst-case. Consider a mutable linked list, implemented so that references to the first and the last element are maintained. Which of the following statements are true? As usual, the length of the list is denoted by n. Random access, meaning reading or writing the ith element, takes constant time. O Mutable stacks can be easily implemented with mutable linked lists. Adding a new element at the end of the list can be done in constant time. □ If each list entry also has a reference to the previous entry, then removing the last element from the list can be done in constant time. The smallest element is always in the beginning of the list and thus finding the smallest element of the list can be done in constant time. O Finding the largest element in the list takes linear time in the worst-case.

icon
Related questions
Question
Consider an arbitrary resizable array that uses expansion factor of 2.0. Which of the following statements are true? The number of elements in the resizable array is denoted by n and the capacity of the underlying low-level array by c. Random access, meaning reading or writing the ith element, takes constant time. O Adding a new element in the beginning takes amortized constant time. Adding a new element at the end takes amortized constant time. If the initial capacity of an empty resizable array is 2 and then 5 elements are inserted at the end, the resulting capacity is 8. Finding the smallest element takes linear time (n) in the worst-case. Finding the largest element takes logarithmic time O(log n) in the worst-case. Consider a mutable linked list, implemented so that references to the first and the last element are maintained. Which of the following statements are true? As usual, the length of the list is denoted by n. Random access, meaning reading or writing the ith element, takes constant time. O Mutable stacks can be easily implemented with mutable linked lists. Adding a new element at the end of the list can be done in constant time. If each list entry also has a reference to the previous entry, then removing the last element from the list can be done in constant time. The smallest element is always in the beginning of the list and thus finding the smallest element of the list can be done in constant time. Finding the largest element in the list takes linear time in the worst-case.
Transcribed Image Text:Consider an arbitrary resizable array that uses expansion factor of 2.0. Which of the following statements are true? The number of elements in the resizable array is denoted by n and the capacity of the underlying low-level array by c. Random access, meaning reading or writing the ith element, takes constant time. O Adding a new element in the beginning takes amortized constant time. Adding a new element at the end takes amortized constant time. If the initial capacity of an empty resizable array is 2 and then 5 elements are inserted at the end, the resulting capacity is 8. Finding the smallest element takes linear time (n) in the worst-case. Finding the largest element takes logarithmic time O(log n) in the worst-case. Consider a mutable linked list, implemented so that references to the first and the last element are maintained. Which of the following statements are true? As usual, the length of the list is denoted by n. Random access, meaning reading or writing the ith element, takes constant time. O Mutable stacks can be easily implemented with mutable linked lists. Adding a new element at the end of the list can be done in constant time. If each list entry also has a reference to the previous entry, then removing the last element from the list can be done in constant time. The smallest element is always in the beginning of the list and thus finding the smallest element of the list can be done in constant time. Finding the largest element in the list takes linear time in the worst-case.
Expert Solution
steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer