Arrays, complexity analysis and searching notes — Unit 1

A data structure is a specialised format for organising, processing, retrieving, and storing data. It is a logical or mathematical model of a particular organisation of data. The choice of data structure depends on the problem to be solved and the operations to be performed.

⇒1.1 Classification of Data Structures

Data structures are broadly classified into two categories: Primitive and Non-Primitive.

• Primitive Data Structures: These are basic structures directly operated upon by machine instructions. Examples: `int`, `float`, `char`, `pointer`.
• Non-Primitive Data Structures: Derived from primitive structures, they focus on grouping homogeneous or heterogeneous data items. Further divided into Linear and Non-Linear.

⇒1.2 Linear vs Non-Linear Data Structures

An Abstract Data Type (ADT) is a theoretical concept that defines a data type mathematically. It specifies the logical properties of a data type and the operations that can be performed on it, but it completely hides the implementation details (i.e., how the data is stored and how the operations are executed).

⇒2.1 Why use ADTs?

• Abstraction: Hides underlying complexity from the user.
• Encapsulation: Groups data and operations together.
• Modularity: Allows changing the implementation without affecting the user code.
• Reusability: The same ADT can be implemented in multiple ways depending on performance needs.

⇒2.2 Example: Stack ADT

The Stack ADT defines a collection of elements with a Last-In-First-Out (LIFO) property. The operations defined are:

• `push(element)`: Inserts an element at the top.
• `pop()`: Removes and returns the top element.
• `peek()` / `top()`: Returns the top element without removing it.
• `isEmpty()`: Returns true if the stack is empty.
• `isFull()`: Returns true if the stack is full (if bounded).

The ADT only states what these functions do. The actual implementation could use an Array (contiguous memory) or a Linked List (dynamic memory).

An algorithm is a finite sequence of unambiguous instructions to solve a specific problem. Algorithm analysis evaluates the performance of an algorithm, primarily focusing on two resources: Time and Space.

• Time Complexity: The amount of time an algorithm takes to run as a function of the input size ($n$).
• Space Complexity: The amount of memory an algorithm requires during its execution as a function of the input size ($n$). Includes both auxiliary space (extra space) and input space.

⇒3.1 Priori vs Posteriori Analysis

⇒3.2 Rate of Growth

The rate of growth describes how the execution time increases with input size. Common growth rates (from best to worst):

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

Asymptotic notations are mathematical tools used to describe the limiting behaviour of a function when the argument tends towards a particular value or infinity. They abstract away constant factors and lower-order terms.

⇒4.1 Big-O Notation ($O$)

Represents the upper bound of an algorithm's time complexity. It gives the worst-case scenario. Formally: $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

⇒4.2 Omega Notation ($\Omega$)

Represents the lower bound. It gives the best-case scenario. Formally: $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$.

⇒4.3 Theta Notation ($\Theta$)

Represents the tight bound. Used when the best-case and worst-case complexities are asymptotically equal. Formally: $f(n) = \Theta(g(n))$ if there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$.

⇒4.4 Little-o and Little-omega ($o$, $\omega$)

• Little-o ($o$): Strict upper bound. $f(n) = o(g(n))$ means $f(n)$ grows strictly slower than $g(n)$.
• Little-omega ($\omega$): Strict lower bound. $f(n) = \omega(g(n))$ means $f(n)$ grows strictly faster than $g(n)$.

The Time-Space Trade-off refers to a situation where the execution time of an algorithm can be reduced at the expense of increased memory usage, or vice versa.

⇒5.1 Examples of Trade-offs

• Hashing vs Linear Search: Hashing uses extra space (hash table) to achieve $O(1)$ average search time, whereas Linear Search uses $O(1)$ extra space but takes $O(n)$ time.
• Merge Sort vs In-place Sorting (Quick/Heap): Merge Sort requires $O(n)$ auxiliary space to merge arrays efficiently, whereas Heap Sort operates in $O(1)$ space but might have slightly higher constant time overheads.
• Dynamic Programming: Storing intermediate results (memoization) takes $O(n)$ or $O(n^2)$ space but can reduce time complexity from exponential $O(2^n)$ to polynomial $O(n^2)$.
• Data Compression: Compressing data saves space but requires extra computation time to compress and decompress.

⇒5.2 Why Space is Often Sacrificed

In modern computing, memory (RAM/storage) is relatively cheap and abundant, whereas processing time directly impacts user experience and server costs. Therefore, it is often considered acceptable to use additional memory (e.g., caching, indexing) to achieve faster execution times.

An Array is a linear data structure that stores a collection of elements of the same data type in contiguous memory locations. It allows random access to elements using their index.

⇒6.1 Characteristics of Arrays

• Homogeneous: All elements must be of the same data type.
• Contiguous Memory: Elements are stored in adjacent memory blocks.
• Random Access: Any element can be accessed in $O(1)$ time if its index is known.
• Static Size (typically): The size of a standard array must be known at compile-time (though dynamic arrays/vectors exist).

⇒6.2 Address Calculation in 1D Arrays

The memory address of an element `A[i]` in a 1D array can be calculated using the formula:

$Address(A[i]) = BaseAddress + (i - LowerBound) \times ElementSize$

• `BaseAddress`: Memory address of the first element (e.g., $A[0]$).
• `i`: Index of the element to find.
• `LowerBound`: Starting index of the array (usually 0 in C/C++/Java).
• `ElementSize`: Size of the data type in bytes (e.g., 4 bytes for a 32-bit `int`).

Example: Let BaseAddress = 1000, ElementSize = 4 bytes, LowerBound = 0. Find Address of `A[3]`.
$Address = 1000 + (3 - 0) \times 4 = 1000 + 12 = 1012$.

A 2D array is an array of arrays, visualised as a matrix with rows and columns. However, computer memory is inherently linear (1D). Therefore, a 2D array must be mapped into linear memory. There are two primary ways to do this: Row-Major Order and Column-Major Order.

⇒7.1 Row-Major Order

In Row-Major Order (used by C/C++/Python), elements are stored row by row. The entire first row is stored in memory, followed by the entire second row, and so on.

Formula for a matrix `A[m][n]` (where $m$ is rows, $n$ is columns):
$Address(A[i][j]) = BaseAddress + [(i - Lr) \times n + (j - Lc)] \times ElementSize$
*(where $Lr$ = Lower bound of rows, $Lc$ = Lower bound of columns, usually 0).*
Assuming 0-indexed: $Address = B + (i \cdot n + j) \cdot S$

⇒7.2 Column-Major Order

In Column-Major Order (used by Fortran/MATLAB), elements are stored column by column. The entire first column is stored, followed by the second column, etc.

Formula for a matrix `A[m][n]`:
$Address(A[i][j]) = BaseAddress + [(j - Lc) \times m + (i - Lr)] \times ElementSize$
Assuming 0-indexed: $Address = B + (j \cdot m + i) \cdot S$

⇒7.3 Example Calculation (Row-Major)

Matrix `A[3][4]`, Base Address = 100, Element Size = 2 bytes. Find Address of `A[2][1]`.
Here $i=2, j=1, n=4$.
$Address = 100 + (2 \cdot 4 + 1) \cdot 2 = 100 + (9) \cdot 2 = 100 + 18 = 118$.

A Sparse Matrix is a matrix in which the majority of the elements are zero. Storing such a matrix in a standard 2D array wastes a significant amount of memory and processing time during operations.

⇒8.1 Why use specialized representations?

• Storage Optimization: Instead of storing $m \times n$ elements, we only store the non-zero elements.
• Computing Time: Matrix operations (addition, multiplication) can skip the zero elements, drastically reducing operations.

⇒8.2 Array Representation (Coordinate List)

The sparse matrix is represented as a 2D array of size $K \times 3$, where $K$ is the number of non-zero elements. Each row stores the `(Row, Column, Value)` of a non-zero element.

The first row typically stores metadata: `(Total Rows, Total Columns, Total Non-Zero Values)`.

Example:
```
Original Matrix (4x4): Sparse Representation:
0 0 3 0 Row Col Value
0 4 0 0 4 4 3 <-- Metadata
0 0 0 5 0 2 3
0 0 0 0 1 1 4
2 3 5
```

Other representations include Linked List representation and Compressed Sparse Row (CSR) format.

Arrays can be effectively used to represent mathematical polynomials. A polynomial is an expression consisting of variables and coefficients, e.g., $P(x) = 5x^4 + 2x^2 + 7$.

⇒9.1 Direct Array Representation

The index of the array represents the exponent, and the value at that index represents the coefficient.

• For $P(x) = 5x^4 + 2x^2 + 7$
• `Array = [7, 0, 2, 0, 5]` (index 0 is $x^0$, index 1 is $x^1$, etc.)

Drawback: Highly inefficient for sparse polynomials like $P(x) = 3x^{100} + 1$. We would need an array of size 101, where 99 elements are zero.

⇒9.2 Array of Structures (Coefficient-Exponent Pairs)

A more space-efficient approach is to use an array of structures, where each structure stores the coefficient and the exponent of a non-zero term.

```c
struct Term {
int coeff;
int exp;
};
struct Term poly[MAX_TERMS];
```

For $P(x) = 5x^4 + 2x^2 + 7$, the array would store: `[{5,4}, {2,2}, {7,0}]`.

This representation makes polynomial addition and multiplication very straightforward and space-efficient.

Standard operations performed on arrays and their time complexities.

⇒10.1 Traversal

Visiting each element of the array exactly once.
Time Complexity: $O(n)$

⇒10.2 Insertion

• At the end: $O(1)$ if capacity allows.
• At a specific index (e.g., beginning): $O(n)$ because all subsequent elements must be shifted right by one position.

⇒10.3 Deletion

• From the end: $O(1)$.
• From a specific index: $O(n)$ because all subsequent elements must be shifted left to fill the gap.

⇒10.4 Updating

Modifying the value at a known index.
Time Complexity: $O(1)$

⇒10.5 Reversing an Array

Can be done in-place using two pointers (start and end). Swap elements at the pointers and move them towards the center.
Time Complexity: $O(n)$, Space Complexity: $O(1)$

Searching is the process of finding the location of a given element (key) within a data structure.

⇒11.1 Linear Search (Sequential Search)

The simplest searching algorithm. It sequentially checks each element of the list until a match is found or the whole list has been searched.

```c
int linearSearch(int arr[], int n, int key) {
for(int i=0; i<n; i++) {
if(arr[i] == key) return i; // Found
}
return -1; // Not found
}
```

⇒11.2 Complexity Analysis

• Best Case Time Complexity: $O(1)$. Occurs when the key is the very first element.
• Worst Case Time Complexity: $O(n)$. Occurs when the key is the last element or not present at all.
• Average Case Time Complexity: $O(n)$. On average, the target will be found in the middle of the array ($n/2$ comparisons).
• Space Complexity: $O(1)$, as it operates in-place.

Advantages: Extremely simple to implement. Works on unsorted data.
Disadvantages: Highly inefficient for large datasets.

Binary Search is a highly efficient searching algorithm that operates on the Divide and Conquer principle.
Prerequisite: The array must be sorted.

⇒12.1 Algorithm Mechanism

• Compare the key with the middle element of the array.
• If they match, return the middle index.
• If the key is smaller than the middle element, repeat the search on the left sub-array.
• If the key is larger, repeat the search on the right sub-array.

```c
int binarySearch(int arr[], int left, int right, int key) {
while(left <= right) {
int mid = left + (right - left) / 2;
if(arr[mid] == key) return mid;
if(arr[mid] < key) left = mid + 1;
else right = mid - 1;
}
return -1;
}
```

⇒12.2 Complexity Analysis

• Best Case Time Complexity: $O(1)$. Occurs when the key is exactly at the middle.
• Worst Case Time Complexity: $O(\log n)$. The search space is halved in each step ($n, n/2, n/4, \dots, 1$).
• Space Complexity: $O(1)$ for the iterative approach. $O(\log n)$ auxiliary stack space for the recursive approach.

Understanding when to use which searching algorithm is critical for system design and interview scenarios.

⇒13.1 Interview Question: Why `mid = left + (right - left) / 2`?

In standard implementations, `mid = (left + right) / 2` is often used. However, if `left` and `right` are very large positive integers, their sum can exceed the maximum value representable by an integer (Integer Overflow).

Using `left + (right - left) / 2` mathematically evaluates to the same value but avoids the overflow issue because the subtraction occurs first.

This concludes Unit 1. Before moving to Linked Lists, ensure you can confidently answer the following university and interview questions.

⇒14.1 University Exam Checklist

• Define Data Structure. Differentiate between Linear and Non-Linear data structures.
• What is an Abstract Data Type (ADT)? Explain with an example.
• Explain Big-O, Omega, and Theta asymptotic notations with their mathematical definitions.
• Derive the formula for calculating the address of an element in a 2D array using Row-Major and Column-Major order.
• What is a Sparse Matrix? Explain its 3-tuple array representation.
• Write a C program to perform Binary Search. Discuss its time complexity.

⇒14.2 Placement Interview Focus

• Given an unsorted array, if you need to perform thousands of searches, should you use Linear Search or sort it and use Binary Search?
• Explain integer overflow in Binary Search.
• How do dynamic arrays (like `std::vector` in C++ or `ArrayList` in Java) resize themselves in memory?
• Given a 2D array, how do you search for an element optimally if both rows and columns are sorted?