Why array was introduced?
So that we don't have to create multiple variables for storing data , example for storing 10 student marks can be stored as variable but the same cannot be replicated for 100 or 1000 marks
How is array stored in memory ?
It is a continuous segment of bytes for example one block will have 1 byte
and 1 address
How much time will it take for below operation?
To access
Array stores the starting address and if we want to fetch ith index
then internally array will do
A[i]-> address of A[0] + i*bytes
so above operation is of constant time as it is basic multiplication
O(1)
To insert
- Usually, it will take O(n) but for a large number this is not the case as amortized complexity -> O(1) Here array size will be increasing by 2X as size will be doubled whenever an array is fully occupied if memory is filled then Memory out of bond exception will be thrown*
To Remove
Removal again takes O(N) time as if one element is removed from the middle of the array then the entire element has to shift and in the worst case, it may take O(N).
What is Sub-Array?
A continuous segment is defined as Sub-array
(i,j) → A[i], A[i+1]....A[j]
What is Sub-sequence?
In this even if some element is removed it will keep the order of remaining elements same is called sub-sequence.number of
sub-array → n*(n+1)/2
aka summation of natural number
Top comments (0)