1. Drag and drop a function name to the appropriate algorithm below (fill in the
ID: 3812330 • Letter: 1
Question
1. Drag and drop a function name to the appropriate algorithm below (fill in the blank with A & B) :
Algorithm blank :
for j = n -1, n - 2, ..., i do
A[ j + 1 ] A[ j ]
A[ i ] e
n n + 1
Algorithm blank :
for j = i+1, i+2, ..., n-1 do
A[ j - 1 ] A[ j ]
n n - 1
A. insert(i, e) B. erase(i)
2. Drag and drop appropriate Big Oh to each operation of a vector with n elements realized by an array(blank), and its storage usage:
Space usage: blank
Operation Time
size() blank
empty() blank
at(i) blank
set(i,e) blank
insert(i,e) blank
erase(i,e) blank
A. O(1) B. O(n)
3.Drag and drop the corresponding step under each picture below(fill in the blank with A & B & C) in order to show the 3 steps to grow an extendable array.
blank:
blank
blank:
A. Copy elements from A to B
B. Reassign A to refer to the new array and delete the old array
C. Create a new array B
Explanation / Answer
Question 1:
The first algorithm is increasing the size of n, using the step n <- n + 1,
which means its insert(i, e), and the second algorithm is decreasing the size of n,
using the step n <- n - 1, which means its erase(i).
Question 2:
size() - This has to count for the number of elements in the array. So, it should traverse
all the array. So, the answer is: O(n).
empty() - This has to see if there is atleast one element in the array. So, it should check
only the first element. So, the answer is: O(1).
at(i) - This has to find the element at ith position. As you're implementing using arrays,
you can simply use the index to extract the element from array. So, the asnwer is: O(1).
set(i, e) - To set an element e in ith position, you're just overwriting the element, and
therefore, the answer is: O(1).
insert(i, e) - To insert an element e in ith position, all the remaining elements after ith
location should be moved to the right to make space. So, the answer is: O(n).
erase(i, e) - To erase an element e in ith position, all the remaining elements after ith
location should be moved to the left to fill the gap. So, the answer is: O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.