Introduction
Open in the Padhaiko app1.1 Introduction to data structures
A data structure is a specialized format for organizing, storing, accessing, and modifying data in computer memory so that algorithms can operate on it efficiently. Before selecting a data structure, we distinguish between a data type and a data structure:
- Data Type: Defines a set of values and the primitive operations permitted on them (such as
int,char,float, anddoublein C). - Data Structure: Organizes multiple data items together with their logical relationships and access mechanisms (such as arrays, linked lists, stacks, queues, trees, and graphs).
Key Specifications of a Data Structure
Every data structure is characterized by four specifications:
- Organization of Data: The logical arrangement of elements and how each element relates to others.
- Accessing Methods: The operations used to retrieve, insert, update, or delete elements.
- Degree of Associativity: The structural links or neighborhood relationships connecting data items.
- Processing Alternatives: The algorithmic strategies supported for traversing, searching, or sorting the stored information.
1.1.1 Need of data structures
In software engineering, program design follows Niklaus Wirth's classic principle:
Choosing the right data structure is essential because the representation of data directly determines how fast an algorithm runs and how much memory it consumes.
1.1.2 Types of data structures and its characteristics
Data structures are classified along two primary axes: primitive vs. non-primitive (with non-primitive further split into linear and non-linear) and static vs. dynamic.
Data Structure
|
+----------------------+----------------------+
| |
Primitive Data Types Non-Primitive Data Structures
(int, char, float, double) |
+--------------+--------------+
| |
Linear Data Structures Non-Linear Data Structures
(Array, Linked List, Stack, Queue) (Tree, Graph, Hash Table)| Aspect | Linear Data Structures | Non-Linear Data Structures |
|---|---|---|
| Arrangement | Elements are arranged sequentially on a single level | Elements are organized hierarchically or as general networks |
| Adjacency | Each element has at most one predecessor and one successor | One element can connect to zero, one, or many other elements |
| Traversal | Traversed completely in a single sequential pass | Requires multi-level or branching traversal (e.g., DFS, BFS, tree orders) |
| Memory Utilization | Contiguous (arrays) or singly/doubly linked nodes | Typically pointer-based or adjacency representations |
| Examples | Array, Linked List, Stack, Queue | Tree, Binary Search Tree, Graph, Hash Table |
Based on memory allocation and capacity flexibility, data structures are also grouped as static or dynamic:
| Characteristic | Static Data Structure | Dynamic Data Structure |
|---|---|---|
| Capacity | Fixed at compile time or creation time | Expands and shrinks dynamically at runtime |
| Memory Allocation | Contiguous block (compile-time or fixed allocation) | Non-contiguous nodes allocated via pointers (malloc/free) |
| Access Pattern | Direct random access by index | Sequential or pointer-following access |
| Insertion / Deletion | Costly in the middle (requires shifting elements) | Efficient once position is located (pointer re-linking) |
| Examples | Static Array | Linked List, Dynamic Stack/Queue, Binary Tree |
1.2 Abstract data type (ADT)
Abstract Data Type (ADT)
An Abstract Data Type (ADT) is a mathematical model for a data structure that specifies:
- The domain of data values stored (value definition), and
- The set of valid operations along with their input parameters, preconditions, and behavioral outcomes (operator definition),
without specifying how the data is stored in memory or how the operations are implemented in code.
As a concrete illustration, a List ADT storing elements of type Element is defined purely by its abstract interface:
- Value Definition: A finite ordered sequence of elements ().
- Operator Definition:
create()creates an empty list ().insert(L, pos, x)inserts at indexpos(), increasing length to .remove(L, pos)deletes and returns the element atpos().get(L, pos)returns the element atposwithout modifying .length(L)andisEmpty(L)query the current size.
1.3 Basics of algorithm design techniques
An algorithm is a finite, unambiguous step-by-step procedure for solving a computational problem. Every valid algorithm must satisfy five fundamental properties:
Five Properties of an Algorithm
- Input: Accepts zero or more well-defined quantities externally.
- Output: Produces at least one verifiable result.
- Definiteness: Every instruction is clear, precise, and unambiguous.
- Finiteness: Terminates after a finite number of steps for all valid inputs.
- Effectiveness: Every operation is basic enough to be executed mechanically in finite time.
Complex problems are solved systematically using eight standard algorithm design techniques:
- Brute Force: Directly enumerates all candidate solutions based on the problem statement and selects the valid or optimal one. Simple to implement for small inputs, though often slow ( or ). Examples: Linear search, exhaustive Traveling Salesman Problem (TSP) over all permutations.
- Divide and Conquer: Splits the problem into independent smaller sub-problems of the same type, solves each recursively, and combines their results. Examples: Binary search (), Merge Sort (), Quick Sort (average ).
- Greedy Algorithms: Builds a solution piece by piece, always choosing the locally optimal option available at that step without reconsidering earlier choices. Fast and simple, though guaranteed globally optimal only for problems with the greedy-choice property. Examples: Kruskal's and Prim's MST algorithms, Dijkstra's shortest path, Huffman coding, activity selection.
- Dynamic Programming (DP): Solves problems exhibiting overlapping subproblems and optimal substructure by solving each unique subproblem once and storing its result—either top-down (memoization) or bottom-up (tabulation). Examples: Fibonacci sequence (), Knapsack, Longest Common Subsequence (LCS).
- Backtracking: Constructs a candidate solution incrementally and abandons (prunes) a partial path as soon as it violates a problem constraint, returning to the previous decision point. Examples: -Queens problem, Sudoku solver, Subset Sum.
- Branch and Bound: Similar to backtracking for combinatorial optimization problems, but computes a cost bound (lower or upper bound) at each node of the state-space tree and prunes branches that cannot improve upon the best solution found so far. Examples: Knapsack optimization, TSP with lower-bound pruning.
- Recursive Algorithms: Expresses the solution of a problem in terms of smaller instances of itself until reaching a terminating base case. Serves as the foundation for divide and conquer, tree traversals, and backtracking. Examples: Factorial, Tower of Hanoi, BST traversals.
- Randomized Algorithms: Incorporates random choices during execution to simplify logic or avoid worst-case inputs.
- Las Vegas: Always returns the exact correct result, while runtime is a random variable (e.g., Randomized QuickSort).
- Monte Carlo: Runs in bounded time, with a small bounded probability of an incorrect result (e.g., Miller–Rabin primality test).
| Technique | Core Strategy | Typical Use Case | Classic Examples |
|---|---|---|---|
| Brute Force | Test all candidates | Small inputs, baseline solution | Linear search, exhaustive TSP |
| Divide & Conquer | Split solve independently merge | Independent subproblems | Merge Sort, Quick Sort, Binary Search |
| Greedy | Pick best local choice at each step | Matroid / greedy-choice optimization | Prim's, Kruskal's, Dijkstra's |
| Dynamic Programming | Cache overlapping subproblems | Optimization with overlapping subproblems | Knapsack, LCS, Floyd–Warshall |
| Backtracking | Incremental search; prune on constraint violation | Constraint satisfaction | -Queens, Sudoku |
| Branch & Bound | State-space search; prune using cost bounds | Optimal combinatorial search | TSP branch-and-bound, Knapsack |
| Recursive | Self-referential decomposition + base case | Naturally self-similar structures | Tower of Hanoi, tree traversals |
| Randomized | Random pivot / sampling choices | Avoiding adversarial worst cases | Randomized QuickSort, Miller–Rabin |
| Aspect | Backtracking | Branch and Bound |
|---|---|---|
| Primary Goal | Find any or all feasible solutions satisfying constraints | Find the optimal (minimum or maximum cost) solution |
| Pruning Criterion | Prunes when constraints are violated (infeasible state) | Prunes both on infeasibility and when cost bound is worse than current best |
| Traversal Order | Typically Depth-First Search (DFS) | BFS, Best-First (least-cost), or DFS |
1.4 Algorithm analysis
Algorithm analysis estimates the computational resources—primarily execution time and memory—required by an algorithm as a function of the input size . Expressing resource usage as a growth function allows us to compare algorithms independently of CPU speed, compiler optimizations, or programming language.
1.4.1 Time and space complexity
Time Complexity and Space Complexity
- Time Complexity : A measure of the number of elementary (basic) operations—such as comparisons, arithmetic operations, or swaps—executed by an algorithm as a function of input size .
- Space Complexity : The total amount of memory required by an algorithm to run to completion, consisting of:
- Fixed Space: Memory independent of (instructions, scalar variables, constants).
- Variable (Auxiliary) Space: Memory dependent on (input arrays, dynamically allocated nodes, and recursion call-stack frames).
To analyze an algorithm systematically:
- Identify the basic operation (the most frequently executed statement, e.g., element comparison in searching/sorting).
- Count how many times the basic operation executes in terms of .
- Express the dominant growth using asymptotic notation (, , ).
| Complexity | Name | Typical Algorithm / Structure |
|---|---|---|
| Constant | Array index access a[i], stack push/pop, fixed scalar variables | |
| Logarithmic | Binary search on a sorted array of items | |
| Linear | Linear search, array traversal, storing an array of elements | |
| Linearithmic | Merge Sort, Heap Sort, Quick Sort (average case) | |
| Quadratic | Bubble Sort, Insertion Sort, Selection Sort, matrix storage | |
| Cubic | Standard matrix multiplication, Floyd–Warshall all-pairs shortest path | |
| Exponential | Recursive Tower of Hanoi ( moves), naive recursive Fibonacci | |
| Factorial | Generating all permutations of items |
1.4.2 Best, worst and average case analysis
Because an algorithm's execution time can depend not only on input size but also on the arrangement of input data, we analyze three distinct cases:
Best, Worst, and Average Case Analysis
- Best Case: The minimum number of operations required for any input of size (most favorable arrangement).
- Linear search: Target is at index comparison .
- Bubble sort (with early-exit flag): Array is already sorted comparisons .
- Worst Case: The maximum number of operations required over all inputs of size (least favorable arrangement). This provides an upper-bound guarantee for every possible input.
- Linear search: Target is at the last index or absent comparisons .
- Bubble sort: Array is reverse-sorted comparisons .
- Average Case: The expected number of operations averaged over a probability distribution of all valid inputs of size .
- Linear search (assuming uniform probability and key present):
1.4.3 Rate of growth
The rate of growth describes how rapidly increases as input size becomes large. For large , the highest-order (dominant) term overwhelms lower-order terms and constant multipliers. For example, in :
- At : (lower-order terms still matter).
- At : vs. — the term contributes over of the total.
Hence, standard asymptotic analysis drops constant factors and lower-order terms, ordering common growth rates from slowest-growing (most efficient) to fastest-growing:
| Input Size | |||||
|---|---|---|---|---|---|
1.4.4 Asymptotic notations: Big Oh, Big Omega and Big Theta
Asymptotic notations provide formal mathematical bounds on positive growth functions as .
Big Oh (O), Big Omega (Ω), and Big Theta (Θ)
Let and be positive-valued functions defined on positive integers :
- Big Oh Notation — (Asymptotic Upper Bound):
grows no faster than beyond threshold . Used primarily to express worst-case upper bounds.
- Big Omega Notation — (Asymptotic Lower Bound):
grows at least as fast as beyond threshold . Used to express best-case or inherent lower bounds.
- Big Theta Notation — (Asymptotic Tight Bound):
Equivalently, if and only if and . is sandwiched tightly between and .
Big-O: f(n) <= c*g(n) Big-Omega: f(n) >= c*g(n) Big-Theta: c1*g(n) <= f(n) <= c2*g(n)
| / c*g(n) | / f(n) | / c2*g(n)
| / | / | / / f(n)
| / f(n) | / c*g(n) | / / / c1*g(n)
| / / | / / | / / /
+---+-+-------------> n +-----+-+-------------> n +-----+-+-------------> n
n0 n0 n0| Notation | Bound Type | Formal Inequality () | Typical Interpretation | Example |
|---|---|---|---|---|
| Upper bound () | Worst-case guarantee | Linear search: | ||
| Lower bound () | Best-case / minimum work | Linear search: | ||
| Tight bound () | Exact asymptotic order | Binary search: |
Worked Examples
1
Using the formal definition of Big-O notation, prove that is , and find valid positive constants and . Verify your bound at and .
Applying the Big-O definition: We must find constants and such that
Bounding each lower-order term by :
Choosing and , the inequality holds for all .
Checking at and :
- At : and , so holds.
- At : holds.
with and (note that smaller constants such as work for larger thresholds like ).
2
Prove using the formal definition of Big-Theta () that , specifying explicit constants , , and .
Stating the condition: We require constants , , and such that
Finding the lower-bound constant : For all , the terms and are strictly positive (), so:
Thus holds for all .
Finding the upper-bound constant : For all , since and :
Thus holds for all .
with , , and , since for all .
3
Analyze the best-case, worst-case, and average-case time complexity (counting key comparisons arr[i] == key) and the space complexity of the C linearSearch function below for an array of size . Also compute the exact average number of comparisons for when the key is equally likely to be at any index.
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i;
}
return -1;
}Best-case and worst-case time complexity:
- Best Case:
keyis located atarr[0]. The loop terminates on the first iteration after comparison . - Worst Case:
keyis atarr[n - 1]or absent from the array. The loop checks all elements .
Average-case time complexity (assuming key is present with uniform probability at each index):
For :
Auxiliary space complexity: The function allocates only the loop variable i (the array pointer arr, n, and key occupy constant parameter space), regardless of . Therefore, auxiliary space complexity is .
- Best case: comparison,
- Worst case: comparisons,
- Average case: comparisons, (for , comparisons)
- Auxiliary space complexity:
4
Determine the exact number of times count++ executes as a function of in the nested loop below, express its tight asymptotic bound (), and verify the exact count for .
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
count++;
}
}Counting inner-loop iterations per outer iteration:
- When , runs from to : execution.
- When , runs from to : executions.
- In general, for outer index , the inner loop executes times.
Summing over to :
Finding the asymptotic bound and evaluating at : Dropping the constant factor and the lower-order term gives . For :
count++ executes times, which is ; for , it executes times.
Exercises
Exercises
Define data structure and distinguish between primitive vs. non-primitive and linear vs. non-linear data structures with two examples of each.
Definition of data structure: A data structure is a systematic way of organizing, storing, and managing data in memory so that operations such as access, insertion, deletion, and searching can be performed efficiently.
Primitive vs. non-primitive data structures:
- Primitive data types are built-in atomic types provided directly by the programming language (e.g.,
int,char,float,double). - Non-primitive data structures are derived structures composed of primitive or other non-primitive elements to represent relationships among data (e.g., arrays, linked lists, trees, graphs).
Linear vs. non-linear data structures:
- Linear data structures store elements in a sequential, single-level order where each element (except the first and last) has a unique predecessor and successor. Examples: Array, Stack (also Linked List, Queue).
- Non-linear data structures store elements hierarchically or as general networks where an element can connect to multiple elements across levels. Examples: Tree, Graph.
A data structure organizes and stores data for efficient access and manipulation. Primitive types (int, char) are language-built atomic values, whereas non-primitive structures compose multiple elements into linear sequences (Array, Stack) or non-linear hierarchies/networks (Tree, Graph).
What is an Abstract Data Type (ADT)? Explain why Stack or List is called an ADT by specifying its value definition and operator definition.
Definition of ADT: An Abstract Data Type (ADT) is a mathematical model that defines a data domain and the permissible operations on that data—along with their preconditions and effects—completely independent of any concrete memory representation or implementation language.
Why Stack is an ADT (Value & Operator Definition):
- Value Definition: A finite ordered collection of elements of a given type arranged such that insertions and deletions occur only at one end called
top. - Operator Definition:
push(S, x): inserts elementxat the top of stackS(providedSis not full).pop(S): removes and returns the top element ofS(providedSis not empty).peek(S): returns the top element without removing it.isEmpty(S)/isFull(S): returns boolean status of stack emptiness or capacity.
Implementation independence: Whether Stack is implemented using a static array (items[MAX]) or a singly linked list, the external behavior of these operations remains identical to the caller.
An ADT defines data values and operations independently of implementation. A Stack is an ADT because its LIFO behavior (push, pop, peek, isEmpty, isFull) is fully specified mathematically without committing to an array or linked-list implementation.
Compare Divide and Conquer, Greedy Algorithms, and Dynamic Programming, giving one classical problem solved by each technique.
Divide and Conquer: Divides a problem into independent (non-overlapping) smaller subproblems, solves each recursively, and merges their solutions. Example: Merge Sort ().
Greedy Algorithms: Makes the locally optimal choice at each step and never backtracks or re-evaluates earlier choices. Works when the problem satisfies the greedy-choice property and optimal substructure. Example: Kruskal's Minimum Spanning Tree or Dijkstra's shortest path.
Dynamic Programming: Solves problems with overlapping subproblems and optimal substructure by solving each subproblem once and storing results in a table (tabulation) or cache (memoization) to avoid recomputation. Example: Knapsack or Longest Common Subsequence.
- Divide & Conquer: Independent subproblems solved recursively and combined (e.g., Merge Sort).
- Greedy: Single locally best choice at every step without backtracking (e.g., Kruskal's MST).
- Dynamic Programming: Caches solutions to overlapping subproblems (e.g., Knapsack).
Define Big-Oh (), Big-Omega (), and Big-Theta () notations formally. Prove that by finding explicit constants and .
Formal definitions (for positive functions ):
- : such that for all .
- : such that for all .
- : such that for all .
Proving : For all , and . Hence:
Choosing and (which is tight at where , and holds strictly for larger such as : and : ) satisfies .
, , and specify asymptotic upper, lower, and tight bounds respectively. For , choosing and proves .
Explain best-case, worst-case, and average-case analysis using Bubble Sort (with an early-exit swapped flag) on an array of elements. Calculate the exact number of element comparisons in the worst case for .
Best case (already sorted array): In the first pass ( comparisons), no swaps occur. The early-exit flag stops the algorithm immediately, giving comparisons .
Worst and average cases:
- Worst case (reverse-sorted array): Pass makes comparisons, pass makes , ..., pass makes comparison. Total comparisons:
- Average case (random order): Roughly half as many swaps and comparisons overall.
Evaluating the worst case for :
Bubble Sort (with early exit) has best case , average case , and worst case with comparisons. For , the worst case performs comparisons.
Arrange the following growth functions in ascending asymptotic order of growth rate: , , , , , , , . Briefly explain why rate of growth ignores constant factors when is large.
Ascending order of growth rates: Comparing values as (for instance, at , , , , , and ):
Why constant factors are ignored for large : Suppose Algorithm A takes steps and Algorithm B takes steps. Although A is slower for , for all , and the ratio grows without bound. Thus the growth-rate class ( vs. ) dominates performance at scale.
Ascending order: . Constant factors only affect small inputs; for large , the dominant growth-rate class determines scalability.