What is the order of each of the following tasks in the worst case? a. Computing
ID: 3687059 • Letter: W
Question
What is the order of each of the following tasks in the worst case?
a. Computing the sum of the first n even integers by using a for loop
b. Displaying all n integers in an array
c. Displaying all n integers in a sorted linked list
d. Displaying all n names in a circular linked list
e. Displaying one array element
f. Displaying the last integer in a linked list
g. Searching an array of n integers for a particular value by using a binary search
h. Sorting an array of n integers into descending order by using a mergesort
i. Adding an item to a stack of n items
j. Adding an item to a queue of n items
Explanation / Answer
(a) Computing the sum of the first n even integers by using a for loop.
Solution: O(n).
(b) Displaying all n integers in an array.
Solution: O(n).
(c) Displaying all n integers in a sorted linked list.
Solution: O(n).
(d) Displaying all n names in a circular linked list.
Solution: O(n).
(e) Displaying one array element.
Solution: O(1). For an array, is very fast to access even the last
array element theArray[n-1].
(f) Displaying the last integer in a linked list.
Solution: O(n). For a (singly) linked list, we have to access every
element from the beginning starting from the head pointer. The code
will look something like this (assuming the list is not empty):
for (ListNode* prev = head; prev->next != NULL;
prev = prev->next)
; // empty body of loop
cout << prev->item;
(g) Searching an array of n integers for a particular value by using a
binary search.
Solution: O(log2 n).
(h) Sorting an array of n integers into descending order by using a mergesort.
Solution: O(n log2 n). Recall that the mergesort algorithm always
has the same number of steps (so there is no best or worst case).
(i) Adding an item to a stack of n items.
Solution: O(1). All that needs to be done is something like this:
newTop = new StackNode;
newTop->item = anItem;
newTop->next = top;
top = newTop;
(j) Adding an item to a queue of n items.
Solution: O(1). All that needs to be done is this (at least in the
case the queue is not empty):
newPtr = new QueueNode;
newPtr->item = anItem;
newPtr->next = NULL;
backPtr->next = newPtr;
backPtr = newPtr;
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.