Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?
Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1)
A sorted array keeps its elements in ascending order in contiguous memory. Its strength is direct access by index; its weakness is that the order must be preserved after every change, which forces elements to shift.
Step 1 — Insertion: the new value must go to its correct sorted position. Even after locating that position by binary search in \(O(\log n)\), all larger elements must move one place right, which costs \(O(n)\) in the worst case.
Step 2 — Deletion: removing an element leaves a gap, and every element after it must move one place left to keep the array contiguous and sorted, again \(O(n)\).
Step 3 — Minimum and maximum: in ascending order the minimum is always at index 0 and the maximum at index \(n-1\), so each is read in \(O(1)\).
Constant-time insertion and deletion would require no shifting, which a sorted array cannot avoid, so the rows claiming 0(1) for those operations fail. The row with 0(n) for maximum and minimum describes an unsorted array, where a full scan is needed; it ignores the benefit of sorting.
Insertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1) option is correct.
Similar Questions
A three dimensional array in ‘C’ is declared as int A[x][y][z]. Here, the address of an item at the location A[p][q][r] can be computed as follows (where w is the word length of an integer) :
When we pass an array as an argument to a function, what actually gets passed ?
Given
int arr[3][4][2]= {{{2,4},{7,8},{3,4},{5,6}},{{7,6},{3,4},{5,3},{2,3}},{{8.9},{7,2},{3,4},{5,1}}};
Which one of the following can be used to refer to element 1 in the above 3-d array?
Consider an array A[20, 10], assume 4 words per memory cell and the base address of array A is 100. What is the address of A[11, 5] ? Assume row major storage.
When an array is passed as parameter to a function, which of the following statements is correct ?
Important Questions from Array
Consider the following C program segment.
#include <stdio.h>
int main()
{
char s1[7] = "1234";
char *p;p = s1 + 2;
*p = '0';printf("%s", s1);
return 0;
What will be printed by the program?
}#include <stdio.h> void foo(int *p, int x){ *p = x; } int main(){ int *z; int a = 20, b = 25; z = &a; foo(z, b); printf("%d", a); return 0; }The output of the given C program is __________. (Answer in integer)- Consider an array $A$ of integers of size $n$. The indices of $A$ run from 1 to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below.
$\forall i,j \in \{1, \dots, n-1\}$ such that $i > j$, $(A[i + 1] - A[i]) > (A[j + 1] - A[j])$
Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem? What is the output the given C language code snippet?
#include<stdio.h>
int main()
{
int x[] = {10,20,30};
int *p = x;
p++;
printf("%d",*p);
return 0;
}
Which of the following expression will delete the entire array pointed to by q?
