Unit 1: Introduction to data structure and algorithms — ITM 252 Data Structure and Algorithms Study Notes

Data Structure: A specialized format for organizing, processing, retrieving, and storing data in computer memory to enable efficient algorithmic operations.
Abstract Data Type (ADT): A mathematical model for data types defined strictly by its behavior and supported operations (e.g. Stack: push, pop, peek) rather than its specific underlying implementation.
Asymptotic Notations:
- Big- $O$ ( $O$ ): Upper bound; worst-case growth rate: $f(n) \le c \cdot g(n)$ for $n \ge n_0$ .
- Big- $\Omega$ ( $\Omega$ ): Lower bound; best-case performance: $f(n) \ge c \cdot g(n)$ .
- Big- $\Theta$ ( $\Theta$ ): Tight asymptotic bound: $c_1 g(n) \le f(n) \le c_2 g(n)$ .

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

Time Complexity Growth Visualization:

Basis of Comparison	Time Complexity	Space Complexity
Metric Measured	Computational CPU operations executed as input size $n$ scales.	Auxiliary memory space allocated (stack + heap) during execution.
Trade-Off	Often minimized by using auxiliary lookup tables (Hash Maps).	Often reduced at the expense of additional CPU recalculation passes.

int sum = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        sum++;
    }
}

Outer loop runs for $i = 0, 1, 2, \dots, n - 1$ .
Inner loop iterations sum:
$0 + 1 + 2 + \dots + (n - 1) = \frac{(n-1)n}{2} = \frac{n^2 - n}{2}$
Drop constants and lower-order terms: $T(n) = O(n^2)$ .

When loops divide by a factor (e.g. for (int i = 1; i < n; i *= 2)), the complexity is $O(\log_2 n)$ , NOT $O(n)$ !

Data Structure and Algorithms