Unit 1: Introduction, searching and sorting
Data Structures notes · PTU syllabus (BSIT302/BSBC302)
On this page
Unit summary
Data structures organise data so that programs run efficiently. This unit covers the basic concept of data, problem analysis, algorithm complexity, Big O notation, the time–space trade-off, types of data structures, linear and binary search, and bubble, insertion and selection sort.
After this unit you can
- Explain data, data structures and their types
- Analyse algorithm complexity using Big O notation and the time–space trade-off
- Implement linear and binary search
- Implement bubble, insertion and selection sort
PTU syllabus topics
- Basic concept of data
- problem analysis
- algorithm complexity
- Big O notation
- time-space trade-off
- types of data structures (arrays, records, pointers, stack, queue, trees, linked list)
- linear and binary search
- bubble/insertion/selection sort
Topic 1
Data, data structures and their types
Data structures are primitive (int, float, char) or non-primitive. Non-primitive structures are linear (arrays, stacks, queues, linked lists) or non-linear (trees, graphs). Common operations are traversal, insertion, deletion, searching, sorting and merging. A data structure is a logical or mathematical model for organising data so it can be stored and processed efficiently.
Primitive
int, float, char, pointer
Linear
Array, linked list, stack, queue
Non-linear
Tree, graph
Static vs dynamic
Fixed size (array) vs grows at run time (linked list)
Common operations: traversing (visiting each element), searching, inserting, deleting, sorting and merging.
- Problem analysis: understand inputs, outputs and constraints, choose a suitable data structure and algorithm, then estimate time and space requirements.
Example
Choosing a structure: a browser's back button uses a stack; a printer's job list uses a queue; a family tree uses a tree; a road map uses a graph.
Exam tip
Classify structures as linear or non-linear with one real-life example each.
Topic 2
Algorithm complexity and Big O notation
The complexity of an algorithm is the amount of time (time complexity) and memory (space complexity) it needs as a function of the input size n.
| Notation | Meaning | Describes |
|---|---|---|
| Big-O, O(f(n)) | Upper bound | Worst case |
| Omega, Ω(f(n)) | Lower bound | Best case |
| Theta, Θ(f(n)) | Tight bound | Exact growth rate |
Common growth rates from fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
Example
Linear search checks up to n elements, so it is O(n); binary search halves the range each step, so it is O(log n).
Time-space trade-off: we can often make a program faster by using more memory (for example a lookup table), or save memory at the cost of speed.
Topic 3
Time–space trade-off
Algorithms are compared by time complexity (how running time grows with input size) and space complexity (how memory grows), usually written in Big-O notation.
- Using more memory can reduce running time, and vice versa — e.g., a lookup table (hash table) answers queries in O(1) time using extra space; recomputing values saves space but takes more time; storing sorted copies speeds searching.
Example
Trading space for time: checking whether a roll number exists by scanning a list of n students takes O(n) time. Storing the roll numbers in a hash table uses extra memory but finds any roll number in about O(1) time.
Exam tip
Common complexities in order: O(1) < O(log n) < O(n) < O(n log n) < O(n²).
Topic 4
Linear and binary search
Binary search works only on a sorted list: compare the key with the middle element and discard half the list each time. It takes O(log n) comparisons, against O(n) for linear search.
- Linear search: check each element one by one until the key is found or the list ends. Works on unsorted data. Best O(1), worst O(n).
- Binary search: works only on sorted data. Compare the key with the middle element; search the left or right half; repeat. Worst case O(log n).
cint binarySearch(int a[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == key) return mid;
else if (key < a[mid]) high = mid - 1;
else low = mid + 1;
}
return -1;
}Example
Binary search for 37 in [5, 12, 19, 25, 37, 44, 58]: mid = 25 (37 > 25, search right half) → [37, 44, 58], mid = 44 (37 < 44, search left) → [37], found in 3 comparisons. Linear search would need 5.
Exam tip
For 1,000 sorted items, binary search needs at most about 10 comparisons.
Topic 5
Bubble, insertion and selection sort
cvoid bubble(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }
}
void insertion(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
}
void selection(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) if (a[j] < a[min]) min = j;
int t = a[i]; a[i] = a[min]; a[min] = t;
}
}Bubble sort
Repeatedly swap adjacent out-of-order pairs
O(n) with early exit, O(n²)
Insertion sort
Insert each element into the sorted part
O(n), O(n²) — good for nearly sorted data
Selection sort
Select the minimum and place it in position
O(n²), O(n²) — fewest swaps
Example
Insertion sort on 5, 2, 4, 1: after passes → 2 5 4 1 → 2 4 5 1 → 1 2 4 5.
Key terms
- Data structure
- Way of organising data for efficient use
- Big O notation
- Upper bound on growth of running time
- Time–space trade-off
- Exchanging memory for speed or vice versa
- Binary search
- Search halving a sorted list each step
- Stable sort
- Sort keeping equal elements in original order
Quick revision
- Primitive vs non-primitive; linear vs non-linear; operations.
- Big O, Ω, Θ; common orders O(1) to O(2ⁿ).
- Time–space trade-off.
- Linear O(n) vs binary O(log n) search.
- Bubble, insertion, selection sort and complexities.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Classify data structures.
- Q2.What is Big O notation?
- Q3.Explain the time–space trade-off.
- Q4.What is the precondition for binary search?
- Q5.Which simple sort is best for nearly sorted data?
- Q6.State the worst-case complexity of bubble sort.
Long-answer questions
- Q1.Explain data structures and their types.
- Q2.Explain algorithm complexity and asymptotic notations.
- Q3.Explain linear and binary search with algorithms.
- Q4.Explain bubble, insertion and selection sort with examples.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures, or to ask about studying B.Sc IT at Synetic.
