Abstract Data Type (ADT)
Definition
An Abstract Data Type (ADT) is a logical or mathematical model of a data structure that
specifies what operations can be performed on the data, without describing how these
operations are implemented.
In simple words:
ADT tells us "What to do," while the Data Structure tells us "How to do it."
Real-Life Example
ATM Machine
When you use an ATM, you perform operations such as:
Withdraw Money
Deposit Money
Check Balance
Change PIN
You do not know how the ATM internally communicates with the bank database.
Here,
ADT = Banking Operations
Implementation = Software, Database, Network, Hardware
ADT Concept
Abstract Data Type (ADT)
┌────────────────────────────┐
│ What Operations? │
│ │
│ • Insert │
│ • Delete │
│ • Search │
│ • Update │
│ • Traverse │
└─────────────┬──────────────┘
│
▼
Data Structure (Implementation)
Array | Linked List | Stack | Queue | Tree
Examples of ADTs
ADT Operations Possible Implementation
List Insert, Delete, Search Array, Linked List
Stack Push, Pop, Peek Array, Linked List
Queue Enqueue, Dequeue Array, Linked List
Priority Queue Insert, Delete Heap
Dictionary (Map) Insert, Search, Delete Hash Table
Example 1: Stack ADT
Operations
Push()
Pop()
Peek()
IsEmpty()
IsFull()
The Stack ADT defines what operations are available.
It does not specify whether the stack is implemented using:
Array
Linked List
Stack Example
Initially
Empty Stack
Push(10)
10
Push(20)
20
10
Push(30)
30
20
10
Pop()
20
10
Example 2: List ADT
Suppose
Student List
Initially
Amit
Neha
Rahul
Insert("Riya")
Amit
Neha
Rahul
Riya
Delete("Neha")
Amit
Rahul
Riya
Search("Rahul")
Output
Found
Whether this list is stored using an Array or a Linked List is hidden from the user.
ADT vs Data Structure
Abstract Data Type (ADT) Data Structure
Logical view Physical implementation
Defines operations Defines storage method
Abstract Data Type (ADT) Data Structure
What to perform How to perform
Independent of implementation Depends on implementation
Example: Stack Array-based Stack, Linked List-based Stack
Advantages of ADT
Hides implementation details.
Improves code reusability.
Simplifies software development.
Makes programs easier to maintain.
Allows implementation changes without affecting users.
Disadvantages of ADT
Slight overhead due to abstraction.
Requires proper implementation.
Can be more complex for beginners.
Applications of ADT
Operating Systems
Database Management Systems (DBMS)
Compiler Design
Artificial Intelligence
Web Browsers
Banking Systems
Airline Reservation Systems
Key Points (Exam-Oriented)
ADT = What operations are performed.
Data Structure = How the operations are implemented.
ADT hides implementation details.
One ADT can have multiple implementations.
Algorithm Analysis, Time & Space Complexity, and Asymptotic Notations
(Engineering Lecture Notes with Examples)
1. Algorithm Analysis
Definition
An algorithm is a finite sequence of well-defined steps used to solve a specific problem.
Algorithm Analysis is the process of evaluating an algorithm to determine how efficiently it
uses time and memory as the input size increases.
Objectives
Compare different algorithms.
Select the most efficient algorithm.
Predict performance for large inputs.
Optimize execution time and memory usage.
Why Analyze Algorithms?
Suppose two algorithms search for an element in a list of 10,000 records.
Algorithm Time Taken
Linear Search 10,000 comparisons
Binary Search 14 comparisons
Algorithm analysis helps us identify the better algorithm before implementation.
Example
Find the maximum number in an array.
Array
15 22 10 45 38
Algorithm
Step 1: max = first element
Step 2: Compare each element with max
Step 3: Update max if a larger element is found
Step 4: Display max
Output
Maximum = 45
Characteristics of a Good Algorithm
Correctness
Efficiency
Simplicity
Finiteness
Definiteness
Generality
2. Time Complexity
Definition
Time Complexity measures the amount of time an algorithm takes to execute as the input
size (n) increases.
It does not measure actual execution time in seconds. Instead, it measures the number of
operations performed.
Example
Algorithm
for(i=0; i<n; i++)
print(i);
If
n=5
Loop executes 5 times.
If
n = 1000
Loop executes 1000 times.
Therefore,
Time Complexity = O(n)
Example
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
print(i,j);
}
Iterations
n × n = n²
Time Complexity
O(n²)
Common Time Complexities
Complexity Name Example
O(1) Constant Access array element
O(log n) Logarithmic Binary Search
O(n) Linear Linear Search
O(n log n) Linear Logarithmic Merge Sort
O(n²) Quadratic Bubble Sort
O(2ⁿ) Exponential Recursive Fibonacci
O(n!) Factorial Travelling Salesman (Brute Force)
Time Complexity Graph
Execution Time
↑
|
| O(n!)
| /
| O(2ⁿ)
| /
| O(n²)
| /
| O(n log n)
| /
| O(n)
|/
| O(log n)
| O(1)
+------------------------------------→ Input Size (n)
3. Space Complexity
Definition
Space Complexity is the total amount of memory required by an algorithm during execution.
It includes:
Input memory
Auxiliary (temporary) memory
Variables
Example 1
int a,b,c;
Memory required is fixed.
Space Complexity = O(1)
Example 2
int arr[n];
Memory depends on input size.
Space Complexity = O(n)
Example
Find the sum of array elements.
sum=0;
for(i=0;i<n;i++)
sum=sum+arr[i];
Extra memory:
sum
i
Only two variables.
Space Complexity = O(1)
Time Complexity vs Space Complexity
Time Complexity Space Complexity
Execution time Memory usage
Number of operations Amount of storage
Depends on input size Depends on variables and data
Example: O(n) Example: O(1)
4. Asymptotic Notations
Definition
Asymptotic Notations describe the growth rate of an algorithm when the input size becomes
very large.
They help compare algorithms independent of hardware or programming language.
Types
1. Big O (O)
2. Big Omega (Ω)
3. Big Theta (Θ)
A. Big O Notation
Definition
Big O represents the upper bound (Worst Case) of an algorithm.
It tells us the maximum execution time.
Example
Linear Search
Search for 50
10 20 30 40 50
Need 5 comparisons.
Worst Case
O(n)
Example
Binary Search
10 20 30 40 50 60 70 80
Worst Case
O(log n)
B. Big Omega (Ω)
Definition
Represents the Best Case.
Minimum number of operations.
Example
Linear Search
10 20 30 40 50
Search for 10
Found immediately.
Best Case
Ω(1)
C. Big Theta (Θ)
Definition
Represents the Average Case.
Average execution time.
Example
Linear Search
Searching random element.
Average comparisons
n/2
Average Complexity
Θ(n)
Comparison of Asymptotic Notations
Notation Meaning Case
Big O Upper Bound Worst Case
Omega (Ω) Lower Bound Best Case
Theta (Θ) Tight Bound Average Case
Example Using Linear Search
Array
15 25 35 45 55
Search 15
Comparisons = 1
Ω(1)
Search 45
Comparisons = 4
Θ(n)
Search 100
Comparisons = 5
O(n)
Real-Life Example
Imagine finding a student's roll number in a class register.
Best Case (Ω): The name is on the first page.
Average Case (Θ): The name is somewhere in the middle.
Worst Case (O): The name is on the last page or not present.
Summary
Algorithm Analysis evaluates an algorithm's efficiency.
Time Complexity measures execution time.
Space Complexity measures memory usage.
Big O (O) → Worst Case.
Big Omega (Ω) → Best Case.
Big Theta (Θ) → Average Case.
Lower complexity generally indicates better performance for large inputs.