1. With respect to resizable arrays, establish the relationship between the size of the array and...

1. With respect to resizable arrays, establish the relationship between the size of the array and the time it takes to perform random access (read a the value stored at a given position somewhere in the array). Provide empirical evidence to support your answer.

Solutions

Expert Solution

A resizable array or dynamic array is an array whose size changes when it becomes full. Generally, the size is doubled each time the insertion is required when array becomes full.

For accessing the element at certain index, the time complexity is always O(1)

In case of searching for a value in each index, the time complexity becomes O(n) in static array.

Considering that the size doubles each time the array exceeds, let us assume that at certain point the array has been doubled k times. Now the size of array becomes 2^k*n.

At this instance the search for a specific value would take at most (2^k*n) steps.
Since n is taken as a very large number for time complexity, 2^k can be considered as a constant for low values of k.
Hence, time complexity becomes O(n).

SUMMARY

For search at an specific index, time complexity is O(1). and
For searching a value in the array, time complexity is O(n).
both in resizabe (dynamic) as well as non-resizable (static) array.

Hope it helps.

venereology answered 4 months ago

Next > < Previous

Related Solutions

In c++ Array expander Write a function that accepts an int array and the arrays size...

In c++ Array expander Write a function that accepts an int array and the arrays size as arguments. The function should create a new array that is twice the size of the argument array. The function should create a new array that is twice the size of the argument array. The function should copy the contents of the argument array to the new array and initialize the unused elements of the second array with 0. The function should return a...

What is an array-based list? What is a resizable list? What is the difference between a...

What is an array-based list? What is a resizable list? What is the difference between a list’s capacity and its size? When a list is expanded, is the size changed or is its capacity changed?

Write a C++ function that accepts array size and pointers to three arrays a1, a2 and...

Write a C++ function that accepts array size and pointers to three arrays a1, a2 and a3 of type float as parameters. It then multiplies a1 and a2 and stored the result in a3. Assume that array multiplication is done by multiplying corresponding array elements, e.g. a3[i] = a1[i] * a2[i] where 0 <= i <= (array size – 1) Write a C++ main program to dynamically create three equal sized float arrays a1, a2 and a3. The size of...

Create a method that gets the difference for a linked bag and a resizable array: Also,...

Create a method that gets the difference for a linked bag and a resizable array: Also, implement the methods in the interface and test out that the program works in the main class //please comment what you are doing for the difference method for the linked bag and the array bag (also explain its time complexity in terms of Big O EX: Bag 1 has : ABC EX: Bag 2 has : ARC the difference is "R" BagInterface public boolean...

Please enter a seed: 1 Please enter the size of the array: 1 Array size must...

Please enter a seed: 1 Please enter the size of the array: 1 Array size must be greater than 1. Please reenter: 0 Array size must be greater than 1. Please reenter: -1 Array size must be greater than 1. Please reenter: 12 Please choose an option: 1 Print the array 2 Find the average 3 Find the largest element 4 Count how many times 3 occurred 5 Count how many elements are less than half of the first element...

In C++ write an implementation of the ADT sorted list that uses a resizable array (vector...

In C++ write an implementation of the ADT sorted list that uses a resizable array (vector class of C++ STL) to represent the list items.

Overlapping Arrays (C++) An array overlaps another array if all elements of the latter array exist...

Overlapping Arrays (C++) An array overlaps another array if all elements of the latter array exist in the former array. They need not necessarily be in the same order. For example, [1,7,3,4,2] overlaps [1,2,3] because 1,2 and 3 exist in [1,7,3,4,2]. To make the implementation easy, [1,7,3,4,2] overlaps [1,1,2,3] as well. We don’t need to check whether 1 appears twice in the first array. Write a program that lets the user enter two arrays and displays whether the first array...

Question: Write an implementation of the ADT sorted list that uses a resizable array (vector class...

Question: Write an implementation of the ADT sorted list that uses a resizable array (vector class of C++ STL) to represent the list items. Anytime the list becomes full, double the size of the array.

1) Write a function searchValue that accepts an array of integers, the size of the array,...

1) Write a function searchValue that accepts an array of integers, the size of the array, and an integer. Find the last occurrence of the integer passed in as an input argument in the array. Return the index of the last occurrence of the value. If the value is not found, return a -1 2) Write the line of code to call the previous function assuming you have an array vec with length n, and are looking for the number...

// Given an array of size 9, with the values of 1-9, determine if the array...

// Given an array of size 9, with the values of 1-9, determine if the array // is valid or not. // Display a message stating the row is VALId, or state its INVALID and what // was the index number that determined the data invalid. // // Use this java code as a start of your code. // Test the array data by changing the values. //============================================================================= import java.util.*; public class Soduko_ValidateRow { public static void main(String...

Subjects