Comprehensive Notes on Data Structures and Algorithm
Analysis
1. Data Types
Data types define the type of data a variable can hold in a programming language. They
help the compiler or interpreter understand how much memory to allocate and how to
interpret the data.
1.1 Primitive Data Types
Primitive data types are the basic built-in types provided by a programming language.
They include: Integer, Float, Character, Boolean, and Void. - Integer: Stores whole
numbers. - Float/Double: Stores decimal numbers. - Character: Stores a single character.
- Boolean: Stores true or false values. - Void: Represents no value or null.
1.2 Non-Primitive Data Types
Non-primitive data types are derived from primitive types. They can store multiple values
or complex data. They include: - Arrays: Collection of elements of the same data type. -
Strings: Sequence of characters. - Structures: Group of variables under one name. -
Classes: Templates that define objects. - Pointers: Variables that store memory
addresses.
2. Algorithm Analysis and Asymptotic Notations
Algorithm analysis measures the efficiency of an algorithm in terms of time and space
complexity. Asymptotic notations describe how an algorithm’s runtime or memory grows
with input size.
2.1 Big O Notation (O)
Describes the upper bound of an algorithm’s growth rate — worst-case scenario. Example:
If an algorithm takes at most 3n² + 2n + 1 operations, O(n²) represents its complexity.
Common examples: - O(1): Constant time - O(log n): Logarithmic time - O(n): Linear time -
O(n log n): Quasi-linear time - O(n²): Quadratic time
2.2 Omega Notation (Ω)
Represents the best-case growth rate or lower bound. Example: If an algorithm takes at
least n operations, then Ω(n).
2.3 Theta Notation (Θ)
Represents the tight bound of an algorithm — when the upper and lower bounds are the
same. Example: If algorithm takes 3n + 2 operations, Θ(n).
2.4 Little o Notation (o)
Describes a non-tight upper bound (looser than Big O). Example: f(n) = o(n²) means f(n)
grows slower than n².
3. Concept of Iteration and Recursion
3.1 Iteration
Iteration means repeating a set of instructions using loops until a condition is false.
Examples: for, while, do-while loops.
Types of Iteration: - Definite Iteration: Number of repetitions known (e.g., for loop). -
Indefinite Iteration: Number of repetitions unknown (e.g., while loop).
3.2 Recursion
Recursion is when a function calls itself directly or indirectly to solve a problem. It must
have: 1. Base Case – condition where recursion stops. 2. Recursive Case – where
function calls itself.
Types of Recursion: - Direct Recursion: Function calls itself. - Indirect Recursion: Function
A calls B, which calls A again. - Tail Recursion: Recursive call is the last statement. -
Non-Tail Recursion: Recursive call not the last statement.
Example: def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)
4. Introduction to Data Structures
Data Structures are ways of organizing and storing data efficiently for access and
modification. They define relationships between data elements and operations on them.
4.1 Linear Data Structures
Elements are arranged sequentially. Examples: - Arrays - Linked Lists - Stacks (LIFO -
Last In First Out) - Queues (FIFO - First In First Out)
4.2 Non-Linear Data Structures
Elements are connected in hierarchical or networked fashion. Examples: - Trees (Binary
Tree, Binary Search Tree, AVL Tree) - Graphs (Directed, Undirected, Weighted,
Unweighted)
Key Difference: - Linear DS: Traversed sequentially (one element after another). -
Non-linear DS: Traversed through multiple paths or branches.
End of Notes