Unit 1 - Notes

CSE205

Unit 1: Introduction, Arrays, Sorting and Searching

1. Basic Concepts and Notations

1.1 Data Structure Defined

A data structure is a specialized format for organizing, processing, retrieving, and storing data. It is a mathematical or logical model of a particular organization of data.

Choice of Data Structure: The choice depends on the underlying operation. For example, looking up a specific item (searching) versus organizing items (sorting).

1.2 Algorithm Defined

An algorithm is a finite set of instructions that, if followed, performs a particular task.
Characteristics:

Input: Zero or more inputs.
Output: At least one output.
Definiteness: Instructions must be clear and unambiguous.
Finiteness: The algorithm must terminate after a finite number of steps.
Effectiveness: Operations must be feasible.

2. Complexity Analysis: Time, Space, and Trade-off

To evaluate an algorithm's efficiency, we analyze its consumption of resources, primarily Time and Space.

2.1 Time Complexity

Time complexity is the amount of computer time it takes to run an algorithm. It is estimated by counting the number of elementary operations performed by the algorithm, assuming that each operation takes a fixed amount of time.

It is expressed as a function of the input size $n$ , denoted as $T(n)$ .

2.2 Space Complexity

Space complexity is the amount of memory space required by the algorithm in its life cycle.
$S(P) = C + S_p$

$C$ : Fixed part (instruction space, simple variables, constants).
$S_p$ : Variable part (dependent on instance characteristics, e.g., recursion stack, dynamic memory).

2.3 Time-Space Trade-off

The Space-Time trade-off states that an algorithm can run faster (less time) if it uses more memory (more space), and vice-versa.

Example: Storing a lookup table (Hash Map) consumes high memory but provides $O(1)$ access time, whereas recalculating values on the fly saves memory but consumes CPU time.

3. Asymptotic Notations

Asymptotic notations are mathematical tools to represent the time complexity of algorithms for asymptotic analysis (how the algorithm performs as input size $n$ grows towards infinity).

3.1 Big O Notation ( $O$ ) - The Upper Bound

Represents the Worst Case scenario. It defines the upper bound of an algorithm's running time.

Definition: $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$ .
Meaning: The algorithm will take at most $c \cdot g(n)$ time.

3.2 Omega Notation ( $\Omega$ ) - The Lower Bound

Represents the Best Case scenario. It defines the lower bound.

Definition: $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$ .
Meaning: The algorithm will take at least $c \cdot g(n)$ time.

3.3 Theta Notation ( $\Theta$ ) - The Tight Bound

Represents the Average Case (or exact bound). It sandwiches the function between upper and lower bounds.

Definition: $f(n) = \Theta(g(n))$ if there exist positive constants $c_1, c_2$ and $n_0$ such that $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$ .
Meaning: The running time grows exactly at the same rate as $g(n)$ .

4. Basic Data Structures

Data structures are generally categorized into two types:

4.1 Primitive Data Structures

Basic structures directly operated upon by machine instructions (e.g., Integers, Floating-point numbers, Characters, Pointers).

4.2 Non-Primitive Data Structures

Derived from primitive data structures.

Linear Data Structures: Elements are arranged in a sequence.
- Arrays: Fixed-size sequential collection.
- Linked Lists: Dynamic sequential collection using pointers.
- Stacks: LIFO (Last In First Out).
- Queues: FIFO (First In First Out).
Non-Linear Data Structures: Elements are arranged hierarchically or interconnectedly.
- Trees: Hierarchical relationship (Parent-Child).
- Graphs: Network relationship (Nodes and Edges).

5. Linear Arrays

5.1 Definition

An array is a collection of homogeneous (same type) data elements stored in contiguous memory locations.

Index: Elements are accessed via an index (subscript).

5.2 Memory Representation of Linear Arrays

In memory, a linear array is stored in consecutive memory cells. The computer needs the address of the first element (Base Address) to calculate the address of any element.

Formula for 1D Array Address Calculation:

LOC(LA[k]) = Base(LA) + w(k - LB)

Where:

$LOC(LA[k])$ : Address of the element at index $k$ .
$Base(LA)$ : Base address (address of the first element).
$w$ : Word size (size of each element in bytes).
$k$ : Index of the element to find.
$LB$ : Lower Bound (index of the first element, usually 0 or 1).

Example:
If Base Address = 2000, $w$ = 4 bytes, $LB$ = 0. Find address of $A[5]$ .

Address = 2000 + 4(5 - 0) = 2000 + 20 = 2020

6. Array Operations and Complexity Analysis

6.1 Traversal

Visiting every element in the array exactly once (e.g., to print or sum).

Algorithm: Iterate from $LB$ to $UB$ (Upper Bound).
Time Complexity: $O(n)$

6.2 Insertion

Adding a new element at a specific position.

Logic: To insert at index $k$ , all elements from $k$ to $n$ must be shifted one position to the right to create space.
Time Complexity:
- Best Case: Insert at end ( $O(1)$ ).
- Worst Case: Insert at beginning ( $O(n)$ ).
- Average: $O(n)$ .

6.3 Deletion

Removing an element from a specific position.

Logic: To delete at index $k$ , all elements from $k+1$ to $n$ must be shifted one position to the left to fill the gap.
Time Complexity: $O(n)$ (due to shifting).

6.4 Merging

Combining two sorted arrays into a single sorted array.

Logic: Compare elements from both arrays (A and B). Place the smaller element into the new array (C) and increment the pointer for that specific array. Repeat until one array is empty, then copy remaining elements.
Time Complexity: $O(n + m)$ , where $n$ and $m$ are sizes of the two arrays.

7. Searching Algorithms

7.1 Linear Search (Sequential Search)

Checks every element in the list sequentially until the desired element is found or the list ends.

Algorithm Logic:
1. Start from index 0.
2. Compare target with array[i].
3. If match found, return i.
4. If end reached without match, return -1.
Requirement: Array does not need to be sorted.
Complexity:
- Best Case: $O(1)$ (Element at first position).
- Worst Case: $O(n)$ (Element at last position or not present).

7.2 Binary Search

A divide-and-conquer algorithm that repeatedly divides the search interval in half.

Requirement: The array MUST be sorted.
Algorithm Logic:
1. Set low = 0, high = n-1.
2. While low <= high:
  1. Calculate mid = (low + high) / 2.
  2. If array[mid] == target, return mid.
  3. If array[mid] < target, ignore left half (low = mid + 1).
  4. If array[mid] > target, ignore right half (high = mid - 1).
3. Return -1 (Not found).
Complexity:
- Best Case: $O(1)$ (Element at mid).
- Worst/Average Case: $O(\log_2 n)$ .

8. Sorting Algorithms

Sorting is the process of arranging data in a specific order (ascending or descending).

8.1 Bubble Sort

Repeatedly swaps adjacent elements if they are in the wrong order. The largest element "bubbles up" to the correct position in each pass.

Steps:
1. Compare $A[0]$ and $A[1]$ . If $A[0] > A[1]$ , swap.
2. Compare $A[1]$ and $A[2]$ , swap if needed.
3. Repeat until end of array. This places the largest number at the end.
4. Repeat the pass for the remaining unsorted part ( $n-1$ , $n-2$ , ...).
Complexity:
- Worst/Average: $O(n^2)$ (Nested loops).
- Best: $O(n)$ (If optimized with a 'swapped' flag and array is already sorted).
- Space: $O(1)$ (In-place).

8.2 Selection Sort

Divides the array into a sorted part (left) and unsorted part (right). It repeatedly finds the minimum element from the unsorted part and puts it at the beginning.

Steps:
1. Assume element at index $i$ is the minimum.
2. Scan from $i+1$ to $n$ . If a smaller value is found, update minimum index.
3. Swap the found minimum with element at index $i$ .
4. Increment $i$ .
Complexity:
- All Cases: $O(n^2)$ (It always scans the remaining list).
- Space: $O(1)$ .

8.3 Insertion Sort

Builds the final sorted array one item at a time. It picks an element and places it into its correct position within the already sorted sub-list.

Steps:
1. Start from the second element (index 1).
2. Compare it with elements before it.
3. Shift elements greater than the key to the right.
4. Insert the key into the correct empty position.
Complexity:
- Worst/Average: $O(n^2)$ .
- Best: $O(n)$ (When the array is already sorted).
- Usage: Very efficient for small datasets or nearly sorted arrays.

8.4 Complexity Comparison Summary

Algorithm	Best Case Time	Average Case Time	Worst Case Time	Space Complexity
Linear Search	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Binary Search	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$
Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$