This is for Java in my Data structures class: 3. Assume that numbers is a large

Question

This is for Java in my Data structures class:

3. Assume that numbers is a large array of integers, currently holding N values in locations 0 through N - 1. Describe the order of magnitude of each of the following operations using Big-O notation: (a) Insert the number 21 into location N of numbers. (b) Shift all values in the numbers array to the "right" one location to make room at location 0 for a new number without disrupting the order of the current values insert the number 21 into location 0. (c) Randomly choose a location L from 0 to N-1; shift all values in the numbers array, from location L to location N - 1, to the right one location to make room at location L for a new number; insert the number 21 into location L

Explanation / Answer

a) To insert element at certain location in an array the logic would be

numbers[N] = 21;

Since we want to insert the element at specific location 'N'., the Big-O complexity of this operation would be O(1) since it doesn't matter how big the array is, it always takes the same constant time to insert the specific item.

b) To shift array elements to right, the logic would be as shown below

/* shifting of array elements to next position */

     for(int i=N-1;i>0;i--)

     {

       numbers[i]=numbers[i-1];

     }

     numbers[0]=21;

In above logic, It would take O(N-1) to loop through all elemets for shifting to the "right" one location and O(1) to insert the number 21 to the first location. So in total the required Big-O complexity would be O(N).

c) To shift array elements from random Lth location to right , the logic would be as shown below.

Here L is any random number between 0 to N-1.

for(int i=N-1;i>=L;i--)

     {

       numbers[i]=numbers[i-1];

     }

     numbers[L]=21;

In above logic, It would take O(L) to loop through all elemets from Lth location for shifting to the "right" location and O(1) to insert the number 21 to the Lth location. So in total the required Big-O complexity would be O(L+1).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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