Give the minimum required running time to execute each of the following operatio

Question

Give the minimum required running time to execute each of the following operations in a sorted Array List in the worst case, using Big- notation, assuming n is the number of elements in the list.

Following each expression, include a 1-2 sentence argument about why an algorithm to perform the given operation could not run faster than the bound you give.

Full credit will be given only for tight Big- bounds. That is, it is not sufficient to say that all operations take (1). This is trivially true for any piece of code. (Though in some cases this will be the tightest Big- bound).

Example Question: Adding a value to the beginning of the array list.

Example Answer: Running time: (n). You have to move everything over one cell to create a room for a new element. It will be done using a for loop that iterates through all elements. Since there are n elements in the list, it takes (n) to add a new element to the beginning of the array list.

-------------------------------------------------------------------------------------------------

1. Reversing the list (content of each node).

2. Adding a value to the end of the list.

3. Removing the value from the list at a given index.

4. Removing the first value from the list.

5. Determining whether the list contains some value v.

Explanation / Answer

1.) Reversing the list will have Big-Omega(n) as we need to perform at least n/2 exchange operations in order to get the reverse of an array list.

2.) Adding a value of the list will have Big-Omega(1) as array is random accessable. Since, we can have index of last element in time of Big-Omega(1). Therefore, overall operation will take Big-Omega(1).

3.) It will take Big-Omega(1) . Best case is when we are deleting the last element from the array. .

4.) Removing the first value from the list wil take Big-Omega(n) as we need to shift the elements to the left after deleting first element.

5.) Determining whether the list contains some value v will take Big-Omega(1) as given element at best can be present at the first index.

Hope it helps. Do give your feedback.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.