Formula Sheets: Arrays

 Page 1


Arra ys F orm ula Sheet
Arra y Basics
• Definition : Con tiguous memory blo c k of fixed size, A[0..n-1] , where n is n um b er of elemen ts.
• Memory Size : S
arra y
=n·S
elemen t
, where S
elemen t
is size of eac h elemen t (e.g., 4 b ytes for in t).
• A ccess Time : O(1) for index-based access, A[i] at memory address B +i·S
elemen t
, where B is
base address.
• Index Range : 0 =i<n , else out-of-b ounds error.
Arra y A ddressing
• 1D Arra y A ddress: A ddr(A[i]) =B +i·S
elemen t
.
• 2D Arra y (Ro w-Ma jor Order) : F or A[m][n] , A ddr(A[i][j]) =B +(i·n+j)·S
elemen t
, where m
is ro ws, n is columns.
• 2D Arra y (Column-Ma jor Order) : A ddr(A[i][j]) =B +(j ·m+i)·S
elemen t
.
• 3D Arra y (Ro w-Ma jor) : F or A[l][m][n] , A ddr(A[i][j][k]) =B +(i·m·n+j ·n+k)·S
elemen t
.
• T otal Elemen ts : N =
?
d
i
, where d
i
is size of dimension i (e.g., m·n for 2D).
Common Arra y Op erations
• Insertion (at index i ) :
– Time Complexit y: O(n) due to shifting elemen ts A[i..n-1] .
– Space Complexit y: O(1) (in-place, assuming arra y has space).
• Deletion (at index i ) :
– Time Complexit y: O(n) due to shifting elemen ts A[i+1..n-1] .
– Space Complexit y: O(1) (in-place).
• T ra v ersal : Time Complexit y: O(n) , Space Complexit y: O(1) .
• Cop y : Time Complexit y: O(n) , Space Complexit y: O(n) for new arra y .
Searc hing in Arra ys
• Linear Searc h :
– Time Complexit y: O(n) , A v erage Comparisons:
n+1
2
.
– Best Case: O(1) (elemen t at index 0).
– Space Complexit y: O(1) .
• Binary Searc h (Sorted Arra y) :
– Time Complexit y: O(logn) , Comparisons: ?log
2
(n+1)? .
– Recurrence: T(n) =T
(
n
2
)
+O(1) , solv es to O(logn) .
– Space Complexit y: O(1) (iterativ e), O(logn) (recursiv e).
1