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
because you have to move the all elements from the insertion index one position to make space for it
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).
🤔 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?
Array is always contiguous.
as @Mysticial said, the C arrays are contiguos. When you do do int arr[3] you are allocating in the stack 3 consecutive ints.
Обсуждают сегодня