For a contiguous data-structure, why is that the access-time is

Question

For a contiguous data-structure, why is that the access-time is

O(1) and the insertion time (to put data in the middle) is O(n)? I can only see logic in the time remaining the same

Help, please

0

25.01.2021

5 ответов

15 просмотров

Mmmmm.....

Contiguous data-structure, we can say it is an array. - Accessing array by given index is O(1), because we can directly read it without enumerating the elements. For example: int a[] = {1, 2, 3, 4}; Accessing a[0], a[1], a[2] and a[3] or even a[n] takes the same time, so it is constant time which is O(1). But inserting data in the middle of array is O(n/2), which is still linear time, we can say O(n) too. This is because we have to shift the elements in order to keep the data well-ordered as we expect. For example: int a[5] = {1, 2, 3, 4}; // a[4] is still unused I want to insert 6 in the middle, so I have to shift 3 and 4 to the right and then put 6 in a[2]. int *p = &a[3]; // shifted index memmove(p, &a[2], sizeof(a) - (sizeof(*a) * 2)); a[2] = 6 The time taken to memmove depends on the number of elements linearly, hence it is O(n). Or precisely O(n/2).

0

25.01.2021

🖖 Автор вопроса

Mmmmm.....
Contiguous data-structure, we can say it is an arr...

🤔 so, let's say: int arr[3]; arr[0] = 3; arr[2] = 4; arr[0] and arr[2] are contiguous, until arr[1] is initialized?

0

25.01.2021

Mmmmm.....

🖖
🤔 so, let's say: int arr[3]; arr[0] = 3; arr[2] =...

Array is always contiguous.

0

25.01.2021