Assume that numbers is a large array of intergers, currently holdong N values in
ID: 669709 • Letter: A
Question
Assume that numbers is a large array of intergers, currently holdong N values in locations 0 through N-1. Describe the order of magnitude of each of the following operations, using Big-O notation: Insert the number 17 into location N of numbers. 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 17 into location 0. Randomly choose a location L from 0 to N-1; shift all the 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 17 into location L.Explanation / Answer
(a)
Complexity = O(1)
Because, we don't have to iterate through the array. We are just putting a number in the memory location 'N' units from the array's first element directly.
(b)
Shifting all values in the array to right by 1 place has O(n) complexity because we would have to iterate through each and every element of the array.
(c)
Shifting all values from index L to N - 1 in the array to right by 1 place has O(n) complexity because we would have to iterate through each and every element of the array after L.